给定一系列的会议时间间隔，包括起始和结束时间[s1,e1]，[s2,e2]，…(si < ei)，确定一个人是否可以参加所有会议。
在线评测地址：领扣题库官网
样例1
输入: intervals = [(0,30),(5,10),(15,20)]
输出: false
解释:
(0,30), (5,10) 和 (0,30),(15,20) 这两对会议会冲突样例2
输入: intervals = [(5,8),(9,15)]
输出: true
解释:
这两个时间段不会冲突题解
-
暴力做法
for i in 1:nfor j in 1:n 判断i j有无交集 判断方法，不妨令i.start<=j.start 若 i.start<=j.start<i.end 就会发生冲突
时间复杂度是O(N^2)从暴力出发，我们想该怎么优化
冲突的判断条件之一是i.start<=j.start
那我们可以先对时间间隔按照左端点升序方式进行排序，那么这个条件肯定是满足了
第二个条件j.start
- 排序+贪心
- 我们先按照左端点对会议时间间隔进行升序排序，如果左端点相同那么就按右端点升序排序
- 从左到右扫描一遍会议时间 并维护当前最大的结束时间maxend，
- 如果i.start因为已经排过序了，令idx的end是maxend
idxidx.start≤i.start证明两个时间间隔有交集，所以返回false
- 有没有可能两个时间有交集，但不符合上面i.startidx和i时间有交集,即
idx.start≤i.start没有交集,即
idx.start因为已经排过序了，所以idx.start≤i.start
所以只要有一个end比i.start大就会发生交集，最容易比i.start大的end肯定是前面最大的一个end
所以不会出现两个时间有交集，但不符合上面i.start所以i.start
复杂度分析：N表示数组的长度
时间复杂度：取决于排序复杂度O(NlogN)，扫描的复杂度O(N)
空间复杂度：并没有多开辟空间，所以还是O(N)的
代码
public class Solution {
/**
* @param intervals: an array of meeting time intervals
* @return: if a person could attend all meetings
*/
public boolean canAttendMeetings(List<Interval> intervals) {
// Write your code here
//按起点排序
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval x, Interval y) {
return x.start - y.start;
}
});
//维护最大的终点
int maxend = -1;
for(int i = 0; i < intervals.size(); i++) {
if(intervals.get(i).start < maxend) {
return false;
}
maxend = Math.max(maxend, intervals.get(i).end);
}
return true;
}
}更多题解参考：九章官网solution
