代码随想录day36【贪心算法】 无重叠区间 划分字母区间 合并区间

无重叠区间

力扣题目链接
思路

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
};

合并区间

力扣题目链接
关键：
判断区间重叠后的逻辑

思路：

1. 先排序
2. 将结果单独保存到数组中，避免在原数组中操作。
3. 与结果数据的最后一个数据进行比较，若重叠，则更新结果数据的右边界。不重叠，直接加入结果数组。

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
};