fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
贪心算法之区间调度问题 :: labuladong的算法小抄
提一个小点：
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];容易发生数据溢出；
Arrays.sort(points, Comparator.comparingInt(t -> t[1]));
这样可以避免排序时return a[1] - b[1];溢出。
@Yggdrasill-7C9 动态规划可以认为是含有重叠子问题的暴力算法，本质还是要穷举所有解空间，而贪心的精髓在于不用穷举所有解空间，就能找到答案。所以准确说应该是，能够用贪心算法解决的问题，一定能用暴力穷举的方式求解。
当然，几乎所有计算机算法问题，都能用暴力穷举的方式求解。。。
关于溢出问题，可使用以下解法
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;
}
}
三种排序方法的对比
// 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
});
东哥，你好，请教一个关于区间调度问题的进阶题的解法，今天大疆的笔试题，没有想到好的方法。 题目的是：输入一个数组，表示一系列的任务，每个任务有一个权重w,开始时间starTime,结束时间endTime。现在要求的是，无时间冲突的情况下的所有调度方式中加权权重和最大的调度方式任务在数组中的索引，也就是在这些任务中，选择一些任务，要求这些任务的时间不能冲突，并且这些任务的权重和加起来最大，然后输出这些任务在原始数组中的索引。 只相到一个回溯方法，要是不考虑权重就可以按照你上面讲解的方式做，现在加了权重感觉不好搞。
东哥，你好，请教一个关于区间调度问题的进阶题的解法，今天大疆的笔试题，没有想到好的方法。 题目的是：输入一个数组，表示一系列的任务，每个任务有一个权重w,开始时间starTime,结束时间endTime。现在要求的是，无时间冲突的情况下的所有调度方式中加权权重和最大的调度方式任务在数组中的索引，也就是在这些任务中，选择一些任务，要求这些任务的时间不能冲突，并且这些任务的权重和加起来最大，然后输出这些任务在原始数组中的索引。 只相到一个回溯方法，要是不考虑权重就可以按照你上面讲解的方式做，现在加了权重感觉不好搞。
有没有相关把权重也当作数组的一个维度 排序呢 ， 然后在之前的二维数组的基础上再扩展出一个维度呢 （只是普通猜测）
东哥，你好，请教一个关于区间调度问题的进阶题的解法，今天大疆的笔试题，没有想到好的方法。 题目的是：输入一个数组，表示一系列的任务，每个任务有一个权重w,开始时间starTime,结束时间endTime。现在要求的是，无时间冲突的情况下的所有调度方式中加权权重和最大的调度方式任务在数组中的索引，也就是在这些任务中，选择一些任务，要求这些任务的时间不能冲突，并且这些任务的权重和加起来最大，然后输出这些任务在原始数组中的索引。 只相到一个回溯方法，要是不考虑权重就可以按照你上面讲解的方式做，现在加了权重感觉不好搞。
有没有相关把权重也当作数组的一个维度 排序呢 ， 然后在之前的二维数组的基础上再扩展出一个维度呢 （只是普通猜测）
那按照你的思路的话，我们到底该怎么排序呢，首先按照权重排序吗？然后再根据开始时间或者结束时间？如果先按照权重排序的话，后面的时间就是无规律的了呀，就不能按照东哥上面讲解的方式解答了呀。
@aristo-panhu 我估计要用 TreeMap + 动态规划来做，穷举所有可能的安排方法求最值。我记得 LeetCode 上好像有类似的题目，有空找出来发在这。
