leetcode57-插入区间

原题

给出一个无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]]

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

解法

思想

直接扫描,找到在哪里插入新区间(或融合区间)。

代码

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int cur = 0;
        boolean hasMerged = false;
        while(cur<intervals.length){
            if(!hasMerged && newInterval[0]<=intervals[cur][1]){
                if(newInterval[1]<intervals[cur][0]){
                    ans.add(newInterval);
                    ans.add(intervals[cur]);
                }
                else{
                    int start = Math.min(newInterval[0],intervals[cur][0]);
                    while(cur<intervals.length&&newInterval[1]>=intervals[cur][0]){
                        cur++;
                    }
                    cur--;
                    ans.add(new int[]{start,Math.max(newInterval[1],intervals[cur][1])});
                }
                hasMerged = true;
            }else ans.add(intervals[cur]);
            cur++;
        }
        if(!hasMerged) ans.add(newInterval);
        int[][] ansArray = new int[ans.size()][2];
        for(int i = 0;i<ans.size();i++){
            ansArray[i] = ans.get(i);
        }
        return ansArray;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode57-%e6%8f%92%e5%85%a5%e5%8c%ba%e9%97%b4/

发表回复

登录后才能评论