一、大纲
给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间
区间调度的问题有不同的应用场景。
- 第一个场景：假设现在只有一个会议室，还有若干个会议，如何将尽可能多的会议安排到这个会议室中。这个问题就是解决最多有几个不重叠区间的问题。利用贪心方法即可。
- 第二个场景：给定若干个会议，会议会有重叠，至少需要申请多少间会议室。这个问题就是解决n个区间的最大重叠数目。
- 第三个场景：给你若干区间，请你将所有有重叠部分的区间进行合并。
- 第四个场景：给你若干区间，其中可能有些区间比较短，被其他区间完全覆盖住了，请你删除这些被覆盖的区间。
- 第五个场景：有两个部门同时预约了同一个会议室的若干时间段，请你计算会议室的冲突时段。
- 第六个场景：给你若干较短的视频片段，和一个较长的视频片段，请你从较短的片段中尽可能少地挑出一些片段，拼接出较长的这个片段
二、场景一：不重叠区间的最大数目
这个场景的解题思路就是将区间数组按照结束时间end排序，不断遍历，删除重叠区间，当有不重叠的区间是进行循环操作。这里用的就是贪心思想：每次选择不重叠且结束时间最早的。因为越早结束越不会冲突。
代码可以参考贪心思想
三、场景二：最大的重叠数
这个题本质是对于每个时间点统计会议数目总量，然后遍历每一个时间点找到最大值。像这种问题直接这样解肯定复杂度是很高的，可以做很多优化。
首先可以用差分数组优化，在 O(1) 的时间复杂度上将整个区间的元素进行加减。这种方式是优化时间数组的记录过程。
然后就是利用扫描线进行优化，不是记录数组，而是利用单个变量扫描时间线，具体步骤是：
- 设置一个变量统计当前时间线的会议数
cnt;
- 不断向后扫描，当遇到任意一个会议的
start时，计数加一cnt++。当遇到任意一个会议的end时，计数减一cnt--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
int minMeetingRooms(int[][] meetings) {
int n = meetings.length;
int[] begin = new int[n];
int[] end = new int[n];
for(int i = 0; i < n; i++) {
begin[i] = meetings[i][0];
end[i] = meetings[i][1];
}
Arrays.sort(begin);
Arrays.sort(end);
// 扫描过程中的计数器
int count = 0;
// 双指针技巧
int res = 0, i = 0, j = 0;
while (i < n && j < n) {
if (begin[i] < end[j]) {
// 扫描到一个红点
count++;
i++;
} else {
// 扫描到一个绿点
count--;
j++;
}
// 记录扫描过程中的最大值
res = Math.max(res, count);
}
return res;
}
|
四、场景三：合并重叠区间
场景三四五都是利用贪心。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
Arrays.sort(intervals, (int[] a, int[] b) -> a[0] - b[0]);
int left = intervals[0][0], right = intervals[0][1];
res.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
if (right < intervals[i][0]) {
res.add(intervals[i]);
left = intervals[i][0];
right = intervals[i][1];
} else {
int[] temp = res.get(res.size() - 1);
right = Math.max(right, intervals[i][1]);
temp[1] = right;
}
}
int[][] ret = new int[res.size()][];
for (int i = 0; i < res.size(); i++) {
ret[i] = res.get(i);
}
return ret;
}
}
|
五、场景四：删除覆盖区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public int removeCoveredIntervals(int[][] intervals) {
if (intervals == null || intervals.length == 0)
return 0;
Arrays.sort(intervals, (int[] a, int[] b) -> {
if (a[0] == b[0])
return b[1] - a[1];
return a[0] - b[0];
});
int cover = 0;
int right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (right >= intervals[i][1]) {
cover++;
} else {
right = intervals[i][1];
}
}
return intervals.length - cover;
}
}
|
六、场景五：区间交集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> resList = new ArrayList<>();
int i = 0, j = 0;
int m = firstList.length, n = secondList.length;
while (i < m && j < n) {
int left = Math.max(firstList[i][0], secondList[j][0]);
int right = Math.min(firstList[i][1], secondList[j][1]);
if (left <= right) {
resList.add(new int[]{left, right});
}
if (firstList[i][1] < secondList[j][1])
i++;
else
j++;
}
int[][] res = new int[resList.size()][];
for (i = 0; i < resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}
}
|
七、场景六：剪视频
同样是一个区间问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public int videoStitching(int[][] clips, int time) {
Arrays.sort(clips, (int[] a, int[] b) -> a[0] - b[0]);
int left = clips[0][0], right = clips[0][1];
int res = 1;
if (left != 0)
return -1;
for (int i = 1; i < clips.length; ) {
if (left == clips[i][0]) {
right = Math.max(right, clips[i][1]);
i++;
} else {
int temp = right;
while (i < clips.length && clips[i][0] <= right) {
temp = Math.max(temp, clips[i][1]);
i++;
}
if (temp == right || right >= time)
break;
right = temp;
res++;
}
}
if (right < time)
return -1;
return res;
}
}
|