LeetCode57-插入区间

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/insert-interval/

中文链接：https://leetcode-cn.com/problems/insert-interval/

题目详述

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

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

示例 1:

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

示例 2:

1
2
3
输入: 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] 重叠。

题目详解

  • LeetCode56-合并区间 是合并区间，本题是插入区间，同样涉及到合并区间的操作。
  • 遍历区间，对于新区间不能与新区间合并的区间，直接按照顺序插入；与新区间能够合并的区间，维护合并后区间的左端点和右端点，最后将合并后的区间插入到正确的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class LeetCode_00057 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        boolean added = false;
        for (int[] interval : intervals) {
            if (interval[1] < newInterval[0]) {
                res.add(interval);
            } else if (interval[0] > newInterval[1]) {
                if (!added) {
                    added = true;
                    res.add(newInterval);
                }
                res.add(interval);
            } else {
                newInterval[0] = Math.min(newInterval[0], interval[0]);
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            }
        }
        if (!added) {
            res.add(newInterval);
        }
        return res.toArray(new int[0][]);
    }
}