一、贪心思想
贪心思想能够应用的前提是题目满足贪心选择性质。贪心选择性质就是每一步做出一个局部最优的选择，最终的结果就是全局最优。
1.1 贪心之区间调度问题
关于区间调度的问题可以参考区间调度
给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。
举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。
这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，请问你今天最多能参加几个活动呢？显然你一个人不能同时参加两个活动，所以说这个问题就是求这些时间区间的最大不相交子集
贪心解法：
1、从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
2、把所有与 x 区间相交的区间从区间集合 intvs 中删除。
3、重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public int intervalSchedule(int[][] intvs) {
if (intvs.length == 0) return 0;
// 按 end 升序排序
Arrays.sort(intvs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
// 至少有一个区间不相交
int count = 1;
// 排序后，第一个区间就是 x
int x_end = intvs[0][1];
for (int[] interval : intvs) {
int start = interval[0];
if (start >= x_end) {
// 找到下一个选择的区间了
count++;
x_end = interval[1];
}
}
return count;
}
|
1.2 题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res = 0;
int i = 0, j = 0;
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
i++;
res++;
}
j++;
}
return res;
}
}
|
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 eraseOverlapIntervals(int[][] intervals) {
if (intervals == null || intervals.length == 0)
return 0;
int res = 1;
Arrays.sort(intervals, (int[] a, int[] b) -> a[1] - b[1]);
// Arrays.sort(intervals, new Comparator<int[]>() {
// public int compare(int[] a, int[] b) {
// return a[1] - b[1];
// }
// });
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
res++;
end = intervals[i][1];
}
}
return intervals.length - res;
}
}
|
使用 lambda 表示式创建 Comparator 会导致算法运行时间过长，如果注重运行时间，可以修改为普通创建 Comparator 语句：
1
2
3
4
5
6
|
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return (o1[1] < o2[1]) ? -1 : ((o1[1] == o2[1]) ? 0 : 1);
}
});
|
实现 compare() 函数时避免使用 return o1[1] - o2[1]; 这种减法操作，防止溢出。