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