题目描述
给定一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,请你判断一个人是否能够参加这里面的全部会议。
// 思考:会议室2如果起点和终点重叠需要额外一个房间,应该如何修改代码
样例
示例 1:
输入:intervals = [[0,30],[5,10],[15,20]]
输出:false
示例 2:
输入:intervals = [[7,10],[2,4]]
输出:true
提示:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106
算法1
(扫描线)
思路:
求区间是否有重叠。可以将区间按start大小排序,然后比较前一个end是否大于后一个start
大于代表有重叠,(好像有一条直线线同时穿过了两个区间,可以看数飞机的图)
时间复杂度 $O(nlogn)$
C++ 代码
#include <vector>
#include <algorithm>
class Solution {
public:
bool canAttendMeetings(std::vector<std::vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i - 1][1] > intervals[i][0]) {
return false;
}
}
return true;
}
};
lambda表达式
这行代码使用了C++11中的lambda表达式(匿名函数)来定义排序比较函数。让我解释一下它的各个部分:
- `sort`:这是C++标准库中的排序算法,用于对容器中的元素进行排序。
- `intervals.begin()` 和 `intervals.end()`:这是表示容器 `intervals` 的开始和结束迭代器。`intervals.begin()` 返回指向容器第一个元素的迭代器,而 `intervals.end()` 返回指向容器尾部(最后一个元素之后)的迭代器。
- `[](const std::vector<int>& a, const std::vector<int>& b)`:这是一个lambda表达式,它定义了一个匿名的比较函数,用于告诉`sort`如何比较两个元素 `a` 和 `b`。
现在来解释lambda表达式的部分:
- `const std::vector<int>& a` 和 `const std::vector<int>& b`:这是lambda表达式的参数列表,表示两个要比较的元素,它们都是 `std::vector<int>` 类型的常量引用。
- `{ return a[0] < b[0]; }`:这是lambda表达式的主体部分,即实际的比较函数。在这里,它比较了两个向量 `a` 和 `b` 的第一个元素,以升序排序。返回的比较结果告诉 `sort` 如何排列这些元素。
因此,这一行代码使用lambda表达式定义了一个自定义的比较函数,以按照区间的开始时间对 `intervals` 容器中的元素进行排序。Lambda表达式的使用使得比较函数的定义更加紧凑和方便。