今天共享的内容是如何用贪心算法，在固定范围内找到更多子区间
问题描绘
现在有多个子区间，区间的范围是从 n 到 m，请在这些区间中，找出最多不彼此掩盖的子区间
const data = [
[6, 8],
[2, 4],
[3, 5],
[1, 5],
[5, 9],
[8, 10],
];
data 是一个二维数组，其中能够找到的最多，不冲突的子区间是：
const spaces = [ [ 2, 4 ], [ 6, 8 ], [ 8, 10 ] ];
思路分析
寻找最多区间的问题，就要请出咱们今天的主角了–贪心算法
贪心算法是一种在许多情况下都能够有效处理问题的算法。它的基本思维是每次挑选当时最优的解,即部分最优解。贪心算法的求解过程是每次挑选当时最优的解,直到满意停止条件。
贪心顾名思义，便是只管眼前的利益，只管着眼前能看见的最优。尽管不好听，可是处理当时的问题却再合适不过了。
关于当时的问题，能够先将各个区间依照左端点排序，然后找下一个区间，要求和当时区间不彼此掩盖，并且区间范围最小。为什么？因为这样能够使剩下的空白区间范围足够大，能够容纳更多的子区间。优先最短，构成部分最优，这便是贪心思维。
说是这么说，看起来挺简略的，可是依照上面的描绘来写代码却不容易。能够换个思路：
对区间的右端点进行升序排序，每加入一个线段，然后挑选后边一个或者多个右端点相同的区间，然后在选中区间内挑选左端点最大的那一条，也便是区间最小的。假如加入今后不会跟之前的区间不会彼此掩盖，那么就加入，不然就继续判别后边的区间
很简略吧，来看看代码咋写
代码实现
//倒序刺进
const insertOrder = (array, value) => {
for (let i = 0; i < array.length; i++) {
if (value[0] >= array[i][0]) {
array[i].splice(i, 0, value);
return;
}
}
array.push(value);
};
// 找到最多的区间
// table是区间表
const findManySpace = (table) => {
table = table.sort((a, b) => a[1] - b[1]);
const res = [];
for (let i = 0; i < table.length; i++) {
let tempArray = [];
let j = i;
// 找到相同右端点的区间
for (; j < table.length; j++) {
// 倒序刺进
if (table[i][1] == table[j][1]) insertOrder(tempArray, table[j]);
else break;
}
i = j - 1;
// res初始可能为空，就不考虑区间掩盖的问题
if (res.length == 0) {
res.push(tempArray[0]);
continue;
}
// 遍历，找到第一个不掩盖的区间
for (let i = 0; i < tempArray.length; i++) {
if (tempArray[i][0] >= res[res.length - 1][1]) {
res.push(tempArray[i]);
break;
}
}
}
console.log(res);
};
代码的思路，也就入上面描绘中所讲的一样，代码就不做具体解说了。
其中有两个需求留意的当地，提一下
- 为了能够快速地在相同右端点的区间中，找到最大左端点的区间，能够选用有序刺进的方式，这样就不用再对
tempArray排序了 - 在找到若干个相同右端点的区间后，需求修改
i的值，表示i前面的区间现已被考虑过了。下一轮循环直接从i后边的区间开端
测试代码
findManySpace(data);
// [ [ 2, 4 ], [ 6, 8 ], [ 8, 10 ] ]
输出正确
总结
本篇文章共享的是一道十分经典的区间求解问题，主要选用的战略是贪心算法。思路很简略，代码也很简略，难的是，假如不看答案之前，这道题底子做不出来….我在说我自己
说句题外话，写完这篇文章，我现已在算法和数据结构专题上共享了 50 余篇文章了，感觉仍在根底打转。数据结构是根底不假，但会了数据结构绝对不代表会算法，算法是解题方法，像数学标题一样，常识是常识，标题是标题，学会了常识，不代表会做标题。并且标题的解法，技巧是另一个层面的东西。
到现在，本专栏共享的数据结构涵盖了大学本科要求的所有数据，从数组，链表，到二叉树，二叉查找树，多叉树，AVL 平衡树，B 树，(红黑树暂时没有)， 图，调集，堆，hash表，共享的算法有排序算法，贪心算法，回溯算法，动态规划，关于浩如烟海的算法问题，这点很不够看。
刚去力扣试了试身手，结果被杀得卸甲归田…我仍是在说我自己
莫非要进入做一道会一道，不做就不会的怪圈么…给自己打了一个问号❓
题外话说完了，有问题能够评论区留言哦。我每天都会共享一篇算法小操练，喜欢就点赞+重视吧
