05 August 2008
Given an array of meeting time 1
intervals
1
intervals[i] = [starti, endi]
Example 1:
1
2
Input: [[0,30],[5,10],[15,20]]
Output: false
Example 2:
1
2
Input: [[7,10],[2,4]]
Output: true
给了一系列会议的时间，问能否同时参见所有的会议，这实际上是求区间是否有交集，朴素解法就是两个for loop，每两个区间比较一下，看是否有overlap，有的话直接返回false。比较两个区间a和b是否有overlap，只用看一个区间的起始位置就好，有两种情况，1）如果a的起始位置大于等于b的起始位置，且a的起始位置小于b的结束位置，那么一定有overlap，2）反过来，如果b的起始位置大于等于a的起始位置，且此时b的起始位置小于a的结束位置，那么也一定有overlap。
先给intervals按照起始时间排个序，然后再只比较起始时间，如果后一个会议的起始时间小于前一个会议的结束时间，返回false，复杂度O(nlogn)会好一点。
这道题利用treemap的特性也可以解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
if (intervals == null || intervals.length == 0) {//没有会议，返回true，可以参加
return true;
}
// 按照会议的开始时间排序
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
// 替代Lambda
// Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 1; i < intervals.length; i++) {//因为需要跟前面的interval比较，所以从index 1开始
// 排序后，检查后一个会议的开始时间是否早于前一个会议的结束时间
if (intervals[i][0] < intervals[i - 1][1]) {
return false;
}
}
return true;
}
}