无重叠区间
力扣题目链接
思路
var eraseOverlapIntervals = function(intervals) {
intervals.sort((a,b)=>{
return a[0]-b[0]
})
let res=0
for(let i=0;i<intervals.length-1;i++){
if(intervals[i+1][0]<intervals[i][1]){
res++
intervals[i+1][1]=Math.min(intervals[i][1],intervals[i+1][1])
}
}
return res
};
划分字母区间
var partitionLabels = function(s) {
let hash={}
for(let i=0;i<s.length;i++){
hash[s[i]]=i
}
let res=[]
let left=0,right=0;
for(let i=0;i<s.length;i++){
right=Math.max(hash[s[i]],right)
if(i===right){
res.push(right-left+1)
left = right+1
}
}
return res
};
合并区间
力扣题目链接
关键：
判断区间重叠后的逻辑
思路：
- 先排序
- 将结果单独保存到数组中，避免在原数组中操作。
- 与结果数据的最后一个数据进行比较，若重叠，则更新结果数据的右边界。不重叠，直接加入结果数组。
var merge = function(intervals) {
if(intervals.length===0)return []
intervals.sort((a,b)=>{
return a[0]-b[0]
})
console.log(intervals)
let res=[]
res.push([...intervals[0]]);
for(let i=1;i<intervals.length;i++){
if(intervals[i][0] <=res[res.length-1][1]){//重叠
res[res.length-1][1]=Math.max(res[res.length-1][1],intervals[i][1])//更新res右边界
}else{
res.push(intervals[i])
}
}
return res
};
