用最少的箭引爆箭头
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
思路
1、排序：将气球按照左边界升序排序
2、什么情况箭数量要增加：points[i][0] > points[i-1][1]
3、怎么判断多个气球是都重叠：更新当前气球有边界。
points[i] = min(points[i][1],points[i-1][1])
求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var findMinArrowShots = function(points) {
if( points.length === 0) return 0
let result = 1
points.sort((a,b)=>{
return a[0] - b[0]
})
for(let i=1;i<points.length;i++){
if (points[i][0]>points[i-1][1]){
result++
}
else{
points[i][1] = Math.min(points[i][1],points[i-1][1])
}
}
return result
};
|
无重叠区间
https://leetcode.cn/problems/non-overlapping-intervals/description/
思路
基本思路和上一题一毛一样
1、排序
2、result = 重叠区间数
求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| var eraseOverlapIntervals = function(intervals) {
if (intervals.length === 0) return 0
let count = 0
intervals.sort((a,b)=>{
return a[0] - b[0]
})
for(let i=1;i<intervals.length;i++){
if(intervals[i][0] < intervals[i-1][1]) {
count++
intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1])
}
}
return count
};
|
合并区间
https://leetcode.cn/problems/merge-intervals/description/
思路
判断 当前区间与前一个区间是否重叠，如果不重叠，将前一个区间加入结果中。如果重叠，修改当前区间的左（最小）右（最大）值。
求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| var merge = function(intervals) {
if(intervals.length === 0) return []
let result = []
intervals.sort((a,b)=>{
return a[0]-b[0]
})
for(let i=1;i<intervals.length;i++){
if(intervals[i][0] > intervals[i-1][1]){
result.push(intervals[i-1])
}
else{
intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1])
intervals[i][0] = intervals[i-1][0]
}
}
result.push(intervals[intervals.length-1])
return result
};
|