252.会议室
给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。
示例 1：输入：intervals = [[0,30],[5,10],[15,20]] 输出：false
示例 2：输入：intervals = [[7,10],[2,4]] 输出：true
分析:
1.只要有重叠那么就不能参加所有会议, 按照开会起点排序, 维护并检查所有末尾扫描点
class Solution {
public:
bool canAttendMeetings(vector<vector<int>>& intervals) {
int n = intervals.size();
if (n <= 0) {
return true;
}
sort(intervals.begin(), intervals.end(), [] (auto a, auto b) {
return a[0] < b[0];
});
for (int i = 1; i < n; ++i) {
if (intervals[i][0] < intervals[i-1][1]) {
return false;
}
}
return true;
}
};
56.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
分析:
1.对所有的区间的左端点先排序
2.新增一个 merged 空数组, 然后遍历排序后的数组, 逐个加入到数组里面, 怎么依次往里面 merge 呢?
(i). 如果当前区间 cur 的左边的端点比 merged 数组中最后一个区间的右端点还大, 那么我们直接放入到 merged 末尾
(ii). 如果当前区间 cur 的左边端点比 merged 数组最后一个 区间 的右端点小, 那么更新最后一个数组的右端点更新成 max(cur右端点, last右端点)
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int len = intervals.size();
vector<vector<int>> merged;
if (len <= 0) {
return merged;
}
auto cmp = [] (const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
};
sort(intervals.begin(), intervals.end(), cmp);
merged.push_back(intervals[0]);
for (int i = 1; i < len; ++i) {
int l = intervals[i][0];
int r = intervals[i][1];
int lastR = merged.back()[1];
// 如果当前区间的左端点 比 最后一个区间的右端点还大, 直接放到最后一个, 没有重合无需合并
if (l > lastR) {
merged.push_back({l, r});
// 否则将 cur区间 和最后一个区间合并
} else {
merged.back()[1] = max(merged.back()[1], r);
}
}
return merged;
}
};
转载请注明来源 goldandrabbit.github.io