Ming
0%

LeetCode-57

Posted on Edited on In

题目

结果

代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 特殊情况
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        if (intervals.length == 1) {
            return specialCase(intervals, newInterval);
        }


        // 新的区间是否已经插入
        boolean inserted = false;
        // 标记状态：是否正在查找区间的终点
        boolean status = false;
        // 存储结果
        List<List<Integer>> ans = new ArrayList<>();

        // 如果新的区间是完全独立的
        if (!haveInCommon(intervals, newInterval)) {
            for (int[] interval : intervals) {
                ans.add(List.of(interval[0], interval[1]));
            }
            ans.add(List.of(newInterval[0], newInterval[1]));
            ans.sort(Comparator.comparingInt(interval -> interval.get(0)));
            return toArray(ans);
        }

        // 否则
        int tmp = 0;
        for (int[] interval : intervals) {
            // 如果新的区间已经被插入
            if (inserted) {
                ans.add(List.of(interval[0], interval[1]));
            } else {
                if (status) {
                    // 如果两个区间有重叠部分
                    if (haveInCommon(interval, newInterval)) {
                        // 只有ON_LEFT这种情况需要考虑
                        if (relation(interval, newInterval) == Relation.ON_LEFT) {
                            ans.add(List.of(tmp, interval[1]));
                            inserted = true;
                            status = false;
                        }
                    } else {
                        ans.add(List.of(tmp, newInterval[1]));
                        ans.add(List.of(interval[0], interval[1]));
                        inserted = true;
                    }
                } else {
                    // 如果两个区间有重叠部分
                    if (haveInCommon(interval, newInterval)) {
                        Relation relation = relation(interval, newInterval);
                        if (relation == Relation.EQUAL) {
                            ans.add(List.of(interval[0], interval[1]));
                            inserted = true;
                        } else if (relation == Relation.CONTAINS) {
                            // 如果是interval包含newInterval
                            if (interval[0] <= newInterval[0] && interval[1] >= newInterval[1]) {
                                ans.add(List.of(interval[0], interval[1]));
                                inserted = true;
                            } else {
                                tmp = newInterval[0];
                                // 标记：正在查找区间终点...
                                status = true;
                            }
                        } else if (relation == Relation.ON_LEFT) {
                            ans.add(List.of(newInterval[0], interval[1]));
                            inserted = true;
                        } else if (relation == Relation.ON_RIGHT) {
                            tmp = interval[0];
                            status = true;
                        }
                    } else {
                        ans.add(List.of(interval[0], interval[1]));
                    }
                }
            }
        }
        if (!inserted) {
            ans.add(List.of(tmp, newInterval[1]));
        }
        return toArray(ans);

    }

    private int[][] toArray(List<List<Integer>> list) {
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < ans.length; i++) {
            ans[i][0] = list.get(i).get(0);
            ans[i][1] = list.get(i).get(1);
        }
        return ans;
    }

    private int[][] specialCase(int[][] intervals, int[] newInterval) {
        int[] interval = intervals[0];
        // 如果两个区间有重叠部分
        if (haveInCommon(interval, newInterval)) {
            return new int[][]{{Math.min(interval[0], newInterval[0]), Math.max(interval[1], newInterval[1])}};
        } else {
            return interval[0] < newInterval[0] ? new int[][]{interval, newInterval}
                    : new int[][]{newInterval, interval};
        }
    }

    // 两个区间是否有重叠部分
    private boolean haveInCommon(int[] interval1, int[] interval2) {
        if (interval1[1] >= interval2[0] && interval1[1] <= interval2[1]) {
            return true;
        }
        if (interval2[1] >= interval1[0] && interval2[1] <= interval1[1]) {
            return true;
        }
        return false;
    }

    // 整个区间和新区间是否有重叠部分
    private boolean haveInCommon(int[][] intervals, int[] interval) {
        for (int[] pair : intervals) {
            if (haveInCommon(pair, interval)) {
                return true;
            }
        }
        return false;
    }

    // 有交集的前提下，判断两个区间的关系
    private Relation relation(int[] interval1, int[] interval2) {
        if (interval1[0] == interval2[0] && interval1[1] == interval2[1]) {
            return Relation.EQUAL;
        }
        if (interval1[0] >= interval2[0] && interval1[1] <= interval2[1]) {
            return Relation.CONTAINS;
        }
        if (interval2[0] >= interval1[0] && interval2[1] <= interval1[1]) {
            return Relation.CONTAINS;
        }
        if (interval2[1] >= interval1[0] && interval2[1] <= interval1[1]) {
            return Relation.ON_LEFT;
        }
        if (interval2[0] >= interval1[0] && interval2[0] <= interval1[1]) {
            return Relation.ON_RIGHT;
        }
        throw new RuntimeException("WTF");
    }
}

enum Relation {
    EQUAL, CONTAINS, ON_LEFT, ON_RIGHT
}

复杂度

时间复杂度：O（n），其中有个sort，但也可以优化到O（n），懒得弄了。

空间复杂度：O（n）