插入区间

发表于
本文字数： 4.9k 阅读时长 ≈ 4 分钟

LeetCode每日一题，57. Insert Interval

先看题目描述

Bc53yF.png

大意就是给定一个无重叠的，按照区间起始端点排序的区间列表，让我们在列表中插入一个新区间，确保区间中的列表仍然有序且不重叠（可以合并区间）

算法和思路

算法流程

我们对所有的区间进行一次遍历，当遍历到区间 [l, r] 时：

  • 如果 r < left，则 [l, r] 与 新区间 S 不重叠且在其左侧，我们可以直接将 [l, r] 加入答案；
  • 如果 l > right，说明 [l, r] 与 S 不重叠且在其右侧，我们可以直接将 [l, r] 加入答案；
  • 否则，说明 [l, r] 与 S 重叠，我们无需将 [l, r] 加入答案，此时，我们需要将 S 与 [l, r] 合并，即将 S 更新为其与 [l, r] 的并集，即执行操作 left = min(l, left)，right = max(r, right)

因此当我们遇到第一个满足 l > right 的区间时，说明以后遍历到的区间不会与 S 重叠，并且它们左端点一定会大于 S 的左端点。此时我们就可以将 S 加入答案。特别地，如果不存在这样的区间，我们需要在遍历结束后，将 S 加入答案

算法源码

模拟

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
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int len = intervals.length;
        if (len == 0) {
            return new int[][]{newInterval};
        }
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;
        List<int[]> ansList= new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[1] < left) {
                ansList.add(interval);
            } else if (interval[0] > right) {
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;
                }
                ansList.add(interval);
            } else {
                left = Math.min(interval[0], left);
                right = Math.max(interval[1], right);
            }
        }
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        int[][] res = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); i++) {
            res[i] = ansList.get(i);
        }
        return res;
    }
}

下面是自己实现的暴力法的代码，基本思路就是遍历然后考虑各种情况，运行效率比较低

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int len = intervals.length;
        if (len == 0) {
            return new int[][]{newInterval};
        }
        boolean flag = false;
        List<int[]> tervals = new ArrayList<>(Arrays.asList(intervals));
        if (newInterval[1] < intervals[0][0]) {
            tervals.add(0, newInterval);
            int[][] res = new int[tervals.size()][2];
            for (int i = 0; i < tervals.size(); i++) {
                res[i] = tervals.get(i);
            }
            return res;
        }
        if (newInterval[0] > intervals[len - 1][1]) {
            tervals.add(len, newInterval);
            int[][] res = new int[tervals.size()][2];
            for (int i = 0; i < tervals.size(); i++) {
                res[i] = tervals.get(i);
            }
            return res;
        }
        for (int i = 0; i < tervals.size(); i++) {
            int[] interval = tervals.get(i);
            if (newInterval[0] >= interval[0] && newInterval[1] <= interval[1]) {
                return intervals;
            } else if (newInterval[0] <= interval[0] && newInterval[1] >= interval[1]) {
                if (flag) {
                    tervals.remove(i);
                    i--;
                } else {
                    interval[0] = newInterval[0];
                    interval[1] = newInterval[1];
                    flag = true;
                }
            } else if (newInterval[0] >= interval[0] && newInterval[0] <= interval[1]) {
                if (flag) {
                    interval[1] = newInterval[1];
                    newInterval[0] = interval[0];
                    tervals.remove(i - 1);
                    i--;
                } else {
                    interval[1] = newInterval[1];
                    newInterval[0] = interval[0];
                    flag = true;
                }

            } else if (newInterval[1] >= interval[0] && newInterval[1] <= interval[1]) {
                if (flag) {
                    interval[0] = newInterval[0];
                    newInterval[1] = interval[1];
                    tervals.remove(i - 1);
                    i--;
                } else {
                    interval[0] = newInterval[0];
                    newInterval[1] = interval[1];
                    flag = true;
                }
                break;
            } else if (i >= 1 && newInterval[0] > tervals.get(i - 1)[1] && newInterval[1] < interval[0]) {
                tervals.add(i, newInterval);
                break;
            }
        }
        int[][] res = new int[tervals.size()][2];
        for (int i = 0; i < tervals.size(); i++) {
            res[i] = tervals.get(i);
        }
        return res;
    }
}