
mzoe666888
V1
2022/06/03阅读:22主题:兰青
内卷大厂系列《贪心-最少需要几个数》
《贪心练习题-最少需要几个数》,您将学到贪心的本质是什么,贪心的常规解法就是利用人类自然智慧去思考,往往利用比较器排序或堆来解题。
一、题目
给定区间的范围[xi,yi]
, xi <= yi , 且都是正整数,找出一个坐标集合Set ,Set中有若干个数字,Set要和每个给定的区间有交集
,求Set中最少需要的几个数。
比如给定区间:[5,8]、[1,7]、[2,4]、[1,9]
,Set最小可以是:{2,6} 或者 {2,5} 或者 {4,5}等满足规则的答案。
二、分析
按照每个序列的xi值从小到大排序,每个序列可以生成2个事件,一个开头事件和一个结尾事件,每个事件包含3个属性,事件以谁开头,事件发生时是开头还是结尾,事件以谁结尾。
比如有4个系列分别是[5,8]、[1,7]、[2,4]、[1,9]
,总共生成8个事件
按照序列的xi值从小到大排序,生成事件结果如下:
(1,开头,7),(1,开头,9),(2,开头,4),(4,结尾),(5,开头,8),(7,结尾),(8,结尾),(9,结尾)

贪心利用人类自然智慧,最常见的做法就是排序(比较器),给定的区间是乱序的,需要以某种机制来排序,把序列区间转化为事件机制,按照假设的事件机制来做。
int[][] ranges
代表序列们,二维数组,总共有N个数列,每个序列表示{xi,yi}
先把所有的序列按照规定的事件进行转化,规定如下:
-
events[i] = {a, b, c} -
a == 0, 表示这是一个区间的开始事件,这个区间结束位置是b -
a == 1, 表示这是一个区间的结束事件,b的值没有意义 -
c表示这个事件的时间点,不管是开始事件还是结束事件,都会有c这个值
所有序列按照xi值从小到大排序,也就是按照时间的c值进行从小到大排序,定义一个容器,如果是开始事件,则添加进容器,如果是结束事件,则需要判断容器是否存在该值,如果存在,则需要此数,必定是之前走过的所有序列中都包含的数字,因为是按照从小到大排序的,这也就是体现贪心的地方。
三、实现
public static int minSet(int[][] ranges) {
int n = ranges.length;
int[][] events = new int[n << 1][3];
for (int i = 0; i < n; i++) {
// [3, 7]
// (0,7,3)
// (1,X,7)
events[i][0] = 0;
events[i][1] = ranges[i][1];
events[i][2] = ranges[i][0];
events[i + n][0] = 1;
events[i + n][2] = ranges[i][1];
}
Arrays.sort(events, (a, b) -> a[2] - b[2]);
// 容器
HashSet<Integer> tmp = new HashSet<>();
int ans = 0;
for (int[] event : events) {
if (event[0] == 0) {
tmp.add(event[1]);
} else {
if (tmp.contains(event[2])) {
ans++;
tmp.clear();
}
}
}
return ans;
}
作者介绍

mzoe666888
V1