贪心算法之区间调度问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：贪心算法之区间调度问题

评论礼仪 见这里，违者直接拉黑。

[xiaozhi007]

提一个小点：

Arrays.sort(intvs, new Comparator<int[]>() {
        public int compare(int[] a, int[] b) {
            return a[1] - b[1];
        }
    });

最好改成后面的这个：
        Arrays.sort(points, (o1,o2)->{
            if(o1[1]>o2[1]) return 1;
            if(o1[1]<o2[1]) return -1;
            return 0;
        });

直接返回return a[1] - b[1];容易发生数据溢出；

[xiaoye-2018]

笔试题，卧槽

[labuladong]

@xiaozhi007 你说的对，这个细节值得注意👍

[z-ak-z]

Arrays.sort(points, Comparator.comparingInt(t -> t[1]));

这样可以避免排序时return a[1] - b[1];溢出。

[DonkeyBoy001]

另外一种写法 Arrays.sort(points, (a,b)-> Integer.compare(a[1],b[1]);

[qihang-dai]

可以按start排序吗？

[polaris-dxz]

贪心算法可以认为是动态规划算法的一个特例
那是否认为所有的贪心解法都可以用动态规划来实现呢？

[labuladong]

@Yggdrasill-7C9 动态规划可以认为是含有重叠子问题的暴力算法，本质还是要穷举所有解空间，而贪心的精髓在于不用穷举所有解空间，就能找到答案。所以准确说应该是，能够用贪心算法解决的问题，一定能用暴力穷举的方式求解。

当然，几乎所有计算机算法问题，都能用暴力穷举的方式求解。。。

[Leloz00]

关于溢出问题，可使用以下解法

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> {
            return Integer.compare(a[1], b[1]);
        });

        int count = 1;
        int end = points[0][1];
        for (int[] point : points) {
            int start = point[0];
            if (start > end) { // 找到不重叠区间（边界重叠也算重叠）
                count++;
                end = point[1];
            }
        }
        return count;
    }
}

[zhongweiLeex]

三种排序方法的对比

        // Arrays.sort(points,(a,b)->(a[1]-b[1]));// 可能出现溢出情况

        // Arrays.sort(points,Comparator.comparingInt(a->a[1]));//升序排序 解决溢出方法2  效率较低 调用内置静态方法， 效率较低
        Arrays.sort(points,(a,b)->{
            if(a[1]>b[1]) return 1;
            if(a[1]<b[1]) return -1;
            return 0;//上述方法可能溢出 解决方法1
        });

[awei-lwj]

sort的排序方法中，用a[1] - b[1]会出现溢出的问题

[steemie]

6666

[deepbreath373]

Arrays.sort(points, (a, b)->(Integer.compare(a[1], b[1])));

[aristo-panhu]

东哥，你好，请教一个关于区间调度问题的进阶题的解法，今天大疆的笔试题，没有想到好的方法。
题目的是：输入一个数组，表示一系列的任务，每个任务有一个权重w,开始时间starTime,结束时间endTime。现在要求的是，无时间冲突的情况下的所有调度方式中加权权重和最大的调度方式任务在数组中的索引，也就是在这些任务中，选择一些任务，要求这些任务的时间不能冲突，并且这些任务的权重和加起来最大，然后输出这些任务在原始数组中的索引。
只相到一个回溯方法，要是不考虑权重就可以按照你上面讲解的方式做，现在加了权重感觉不好搞。

[gtbai]

Wikipedia上有这个问题的答案：https://en.wikipedia.org/wiki/Interval_scheduling#Weighted

[zhongweiLeex]

东哥，你好，请教一个关于区间调度问题的进阶题的解法，今天大疆的笔试题，没有想到好的方法。 题目的是：输入一个数组，表示一系列的任务，每个任务有一个权重w,开始时间starTime,结束时间endTime。现在要求的是，无时间冲突的情况下的所有调度方式中加权权重和最大的调度方式任务在数组中的索引，也就是在这些任务中，选择一些任务，要求这些任务的时间不能冲突，并且这些任务的权重和加起来最大，然后输出这些任务在原始数组中的索引。 只相到一个回溯方法，要是不考虑权重就可以按照你上面讲解的方式做，现在加了权重感觉不好搞。

有没有相关把权重也当作数组的一个维度 排序呢 ， 然后在之前的二维数组的基础上再扩展出一个维度呢 （只是普通猜测）

[aristo-panhu]

东哥，你好，请教一个关于区间调度问题的进阶题的解法，今天大疆的笔试题，没有想到好的方法。 题目的是：输入一个数组，表示一系列的任务，每个任务有一个权重w,开始时间starTime,结束时间endTime。现在要求的是，无时间冲突的情况下的所有调度方式中加权权重和最大的调度方式任务在数组中的索引，也就是在这些任务中，选择一些任务，要求这些任务的时间不能冲突，并且这些任务的权重和加起来最大，然后输出这些任务在原始数组中的索引。 只相到一个回溯方法，要是不考虑权重就可以按照你上面讲解的方式做，现在加了权重感觉不好搞。

有没有相关把权重也当作数组的一个维度 排序呢 ， 然后在之前的二维数组的基础上再扩展出一个维度呢 （只是普通猜测）

那按照你的思路的话，我们到底该怎么排序呢，首先按照权重排序吗？然后再根据开始时间或者结束时间？如果先按照权重排序的话，后面的时间就是无规律的了呀，就不能按照东哥上面讲解的方式解答了呀。

[labuladong]

@aristo-panhu 我估计要用 TreeMap + 动态规划来做，穷举所有可能的安排方法求最值。我记得 LeetCode 上好像有类似的题目，有空找出来发在这。

[MzxlM]

@aristo-panhu 我思考了一下能不能在做贪心排序的同时用dp 穷举所有可能的组合取最大值？

[yonggui-yan]

打卡打卡。滴滴滴

贪心：局部最优》〉》〉》全局最优

区间尾部最小的应该先完成！

[chenxiiang]

按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
按照左边界排序，就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。

[johnnylius]

不知道大家有没有疑问这和贪心有什么关系，因为是求最多能参加几个活动，找到活动最早结束的，这样就能赶紧参加下一个活动，就能参加更多活动，这还不够贪心吗？

[Hyuvo]

435

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        // lambda expresion comparator
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int end = intervals[0][1];
        int count = 0;
        // start from the 2nd interval
        for (int i = 1; i < n; ++i) {
            int start = intervals[i][0];
            // if overlaps, count
            if (start < end) {
                count++;
            } else {
                // if no overlap, move forward
                end = intervals[i][1];
            }
        }
        return count;
    }
}

[3315531721]

1

[CarlLy7]

打卡，现在这个重叠区间问题改了，附上注释详细的Java代码

    public int eraseOverlapIntervals(int[][] intervals) {
        //根据每个区间的end进行一个升序排列，我们要保证后面的序列的start是大于等于这个区间的结尾才能说明这两个区间是没有交集的
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[1] > o2[1]) {
                return 1;
            }
            if (o1[1] < o2[1]) {
                return -1;
            }
            return 0;
        });
        //count来记录没有交集的区间，最后的结果就是intervals元素的个数减去这个没有交集的区间个数就好了
        int count = 1;
        //开始的end肯定是end最小的那个
        int start_end = intervals[0][1];
        for (int[] interval : intervals) {
            int start = interval[0];
            if (start >= start_end) {
                //如果后面的区间的start是比此时的start_end大或者等于的时候，说明两个区间也是没有交集的
                count++;
                //更新start_end的大小
                start_end = interval[1];
            } else {
                //如果两个区间有交集的话，什么都不做
            }
        }
        return intervals.length - count;
    }