为什么要学习算法？因为 「程序=数据结构+算法」 ，这是在面向过程的编程语言年代备受推崇的一句话，拥有良好的算法基础才能在人群之中脱颖而出。人们设计各种算法的目的是解决现实问题，所以学好算法才能站在一个更高维度来看待问题，我们在本篇文章介绍一个经典的算法 — 贪心算法。
什么是贪心算法贪心选择的性质：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
举个例子：
- 捡金条
面前堆满了金条，但是你只能拿五条，如何保证能收益最大化？
答案肯定是每次都拿剩下中最大的那一条。这就符合 在某种意义上的局部最优解。
- 斗地主的提示功能
相信玩过 QQ游戏 中斗地主的都知道，在出牌时，我们有一个 托管的功能 。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XK5Ow0Tr-1654157617237)(https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/4caba7cd5c2c4178bb4279041fb20ee6~tplv-k3u1fbpfcp-zoom-in-crop-mark:1956:0:0:0.image?)]
比如：
上家出了一个 3 。
我手中的牌有：345678 大王 ，这 7 张牌。
此时，通过 托管 功能，我们出了 4 。
手下剩的牌：35678 大王。
虽然我们知道局部最优的肯定是用 4 打 3，但是 剩下的 35678 就连不成对子了。这就造成了在全局来说不算最优的结果呢，这就是贪心算法的缺点。
好了，讲了那么多，相信大家应该也知道贪心算法的好处和坏处是什么了。
区间调度有了上述的铺垫，我们来看一个经典的贪心算法问题 区间调度。
题目：有许多 [start,end] 的闭区间，请设计一个算法，算出这些区间中，最多有几个互不相交的区间。
比如 intvs = [ [1,3], [2,4]，[3,6] ]
这些区间最多有两个区间互不相交，即 [1,3], [3,6]，intervalSchedule 函数此时应该返回 2 。
function intervalSchedule (intvs) {}
❓ 贪心猜测
-
张三今天有好几个活动要参加，每个活动的时间可以用区间表示 [start, end]。
-
每次都选择区间中开始时间最早的那个吗？
答案是不行，因为有的区间可能开始很早，结束时间却很晚，例如：[0, 10], [1, 2], [2, 3]。
-
每次都选择时间最短的那个？
答案也是不行，区间有可能会相交，例如：[1, 3], [2, 4], [3, 6]，时间最短的是[1, 3], [2, 4]，但是他们相交了。
-
既然以上的猜测都不对，那应该怎么办呢？
正确的思路应该是：
- 从可选区间 intvs 里，选择一个结束时间最小的区间（用 x 表示）。
- 把所有与 x 相交的区间从 intvs 里去掉。
- 重复 1 和 2 ，直到把 intvs 给清空。
看一张图：
上图分别对应 [1, 3], [2, 4], [3, 6]，这几个区间。相交是什么意思呢？ 其实就是我跟你的区间里有公共的部分，就是相交。上图中 [1, 3], [2, 4] 之间 不就是 2 到 3 之间有公共的部分嘛。问题来了，怎么样才不会相交呢？ 看上图可以明确的知道，如果我的 start 比你的 end 大的话（相等的话也算作不相交），那么我们是不是就不会相交啦。
代码实现function interval (intvs) {
if (intvs.length === 0) return 0;
// 把区间按 end 升序（从小到大）
// 拿到第一个区间的 end
// 定义计数器 count = 1
// 遍历
// 拿到第一个区间的 start
// 如果 start 大于等于 第一个区间的 end，那么计数器 +1
// 把当前区间的 end 赋值给 xEnd，继续下一次循环
}
先把思路用伪代码的形式写出来，这样的好处多多哦，希望大家可以有这样的习惯~~
这里指的注意的是：为什么 计数器 不是从 0 开始呢？ 因为互不相交的区间至少会有一个。
具体代码实现：
function interval (intvs) {
if (intvs.length === 0) return 0;
// 把区间按 end 升序（从小到大）
const sort = intvs.sort((a, b) => a[1] - b[1]);
// 拿到第一个区间的 end
let xEnd = sort[0][1];
// 定义计数器 count = 1
let count = 1;
// 遍历
// 拿到第一个区间的 start
// 如果 start 大于等于 第一个区间的 end，那么计数器 +1
// 把当前区间的 end 赋值给 xEnd，继续下一次循环
for (let item of intvs) {
let start = item[0];
if (start >= xEnd) {
count++;
xEnd = item[1];
}
}
return count;
}
✨总结
以上就是本次分享的全部内容~~
如果觉得文章写得不错，对你有所启发的，请不要吝啬 点个 赞 和 关注 并在 评论区 留下你宝贵的意见哦~~
} }
return count;
}
