今天的三道题目，都算是 重叠区间 问题，大家可以好好感受一下。 都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！
这种题还是属于那种，做过了也就会了，没做过就很难想出来。
不过大家把如下三题做了之后， 重叠区间 基本上差不多了
- 用最少数量的箭引爆气球
https://programmercarl.com/0452.用最少数量的箭引爆气球.html
/**
* @param {number[][]} points
* @return {number}
*/
var findMinArrowShots = function(points) {
points.sort((a,b)=>{
if (a[0]!==b[0]) {
return a[0]-b[0]
} else {
return a[1] - b[1];
}
});
let res = 1;
for (let i=1;i<points.length;i++) {
if (points[i][0] > points[i-1][1]) {
res++;
} else {
points[i][1] = Math.min(points[i][1], points[i-1][1])
}
}
return res;
};
- 无重叠区间
https://programmercarl.com/0435.无重叠区间.html
跟上一题类似，但需要一个变量记录上一轮的重叠右边界
/**
* @param {number[][]} intervals
* @return {number}
*/
var eraseOverlapIntervals = function(intervals) {
intervals.sort((a, b)=>{
if (a[0] !== b[0]) {
return a[0] - b[0];
} else {
return a[1] - b[1];
}
})
let res = 0;
let end = intervals[0][1];
for (let i=1;i<intervals.length;i++) {
if (intervals[i][0] < end) {
res++;
end = Math.min(intervals[i][1], end)
} else {
end = intervals[i][1]
}
}
return res;
};
763.划分字母区间
https://programmercarl.com/0763.划分字母区间.html
有思路，但写不出来
/**
* @param {string} s
* @return {number[]}
*/
var partitionLabels = function(s) {
const sArr = new Array();
for (let i=0;i<s.length;i++) {
let index = s[i].charCodeAt() - 'a'.charCodeAt();
sArr[index] = i;
}
let index = 0;
const res = [];
let prev = 0
for (let i=0;i<s.length;i++) {
let ind = s[i].charCodeAt() - 'a'.charCodeAt()
index = Math.max(index, sArr[ind]);
if (i === index) {
res.push(i + 1 - prev);
prev = i+1;
}
}
return res;
};