1. 代码段小站首页
  2. 算法

leetcode57-插入区间

彭晨涛 • • 算法 • 阅读 26

原题

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

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

示例 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/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年5月12日 00:28
下一篇 2020年5月13日 00:22

相关推荐

发表回复

登录后才能评论