【C++刷题】力扣-#252-会议室
题目描述
给定一个会议时间安排的数组 intervals，每个 intervals[i] 表示一个会议的开始和结束时间。判断一个人是否能够参加所有的会议（即没有会议是重叠的）。
示例
示例 1:
输入：intervals = [[0,30],[5,10],[15,20]]
输出：false
示例 2:
输入：intervals = [[7,10],[9,12]]
输出：true
题解
这个问题可以通过排序和贪心算法来解决。
- 排序：首先根据会议的开始时间对 intervals 进行排序。
- 检查重叠：遍历排序后的会议时间，对于每个会议，检查它的开始时间是否大于或等于前一个会议的结束时间。
○ 如果是，说明没有重叠，继续检查下一个会议。
○ 如果不是，说明存在重叠，返回 false。 - 返回结果：如果所有会议检查完毕，没有发现重叠，返回 true。
代码实现
bool canAttendMeetings(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] < intervals[i-1][1]) {
return false;
}
}
return true;
}
复杂度分析
● 时间复杂度：O(n log n)，其中 n 是会议的数量。主要时间消耗在排序上。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法的优势在于它的时间效率较高，只需要一次遍历即可判断所有会议是否冲突，且不需要额外的存储空间。