通用思路
1、区间的定义：二维数组，每个元素长度为2，分别表示起始和终止点。
2、将区间按照起始点从小到大排序（或者按照终止点排序）。
1
2
3
4
5
6
7
8
9
|
Arrays.sort(intervals, new Comparator<>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
|
3、循环遍历处理区间，前一个区间为蓝色，后一个区间为绿色，两者有如下三种情况。
![]()
题目
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
1
2
3
| 输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
|
示例 2:
1
2
3
| 输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
|
解答
合并区间取并集。
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
| class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null intervals.length <= 1) {
return intervals;
}
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
List<int[]> result = new LinkedList<>();
int[] pre = intervals[0];
for (int i = 1; i < intervals.length; ++i) {
int[] cur = intervals[i];
if (cur[0] > pre[1]) {
result.add(pre);
pre = cur;
}
else if (cur[1] <= pre[1]) {
}
else {
pre[1] = cur[1];
}
}
result.add(pre);
return result.toArray(new int[0][0]);
}
}
|
题目
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example:
1
2
3
4
5
6
7
8
| 输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2
解释:
可以用2支箭，x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
|
解答
合并区间取交集。合并后的每个重叠区间范围内用一支箭（注意，重叠区间的起点和终点可以相同）。
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 findMinArrowShots(int[][] points) {
if (points == null points.length == 0) {
return 0;
}
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
int[] pre = points[0];
int count = 1;
for (int i = 1; i < points.length; ++i) {
int[] cur = points[i];
if (cur[0] > pre[1]) {
++count;
pre = cur;
} else if (cur[1] <= pre[1]) {
pre[0] = cur[0];
pre[1] = cur[1];
} else {
pre[0] = cur[0];
}
}
return count;
}
}
|
题目
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意：
- 可以认为区间的终点总是大于它的起点。
- 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
1
2
3
4
5
| 输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
|
示例 2:
1
2
3
4
5
| 输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
|
示例 3:
1
2
3
4
5
| 输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
|
解答
删除区间。贪心思想，遍历区间，每次遇到重叠时删除end更大的区间，尽可能避免其与下一个区间的start发生重叠。
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 eraseOverlapIntervals(int[][] intervals) {
if (intervals == null intervals.length <= 1) {
return 0;
}
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
int delete = 0;
int[] pre = intervals[0];
for (int i = 1; i < intervals.length; ++i) {
int[] cur = intervals[i];
if (cur[0] >= pre[1]) {
pre = cur;
}
else if (cur[1] > pre[1]) {
delete++;
}
else {
pre = cur;
delete++;
}
}
return delete;
}
}
|
