LC.P57[插入区间]

方法一：排序+区间合并

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
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] newIntervals = new int[intervals.length + 1][2];
        for (int i = 0; i < intervals.length; ++i) {
            newIntervals[i] = intervals[i];
        }
        newIntervals[intervals.length] = newInterval;
        return merge(newIntervals);
    }
    
    // LC.P56[合并区间]
    private int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; ++i) {
            int start = intervals[i][0], end = intervals[i][1];
            if (ans.get(ans.size() - 1)[1] < start) {
                ans.add(intervals[i]);
            } else {
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], end);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$

方法二：一次遍历

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
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int newStart = newInterval[0], newEnd = newInterval[1];
        boolean flag = false;
        for (int[] interval : intervals) {
            int start = interval[0], end = interval[1];
            if (newEnd < start) {
                if (!flag) {
                    ans.add(new int[]{newStart, newEnd});
                    flag = true;
                }
                ans.add(interval);
            } else if (end < newStart) {
                ans.add(interval);
            } else {
                newStart = Math.min(newStart, start);
                newEnd = Math.max(newEnd, end);
            }
        }
        if (!flag) {
            ans.add(new int[]{newStart, newEnd});
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$