coding-problems/src/main/java/com/leetcode/intervals/InsertInterval.java at 13a5b4018f1b7e1db43c4b20559eabe75a944e95 · unrealwork/coding-problems · GitHub

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
package com.leetcode.intervals;

import java.util.ArrayList;
import java.util.List;

final class InsertInterval {
    private InsertInterval() {
    }

    @SuppressWarnings("squid:S3012")
    static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int i = 0;
        while (i < intervals.length && !isOverlap(intervals[i], newInterval)) {
            res.add(intervals[i]);
            i++;
        }
        if (i == intervals.length) {
            if (intervals.length == 0) {
                res.add(newInterval);
            } else {
                int j = 0;
                while (j < intervals.length && intervals[j][0] < newInterval[0]) {
                    j++;
                }
                res.add(j, newInterval);
            }
        }

        if (i < intervals.length) {
            int[] mergedInterval = new int[2];
            mergedInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            mergedInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
            while (i < intervals.length && isOverlap(intervals[i], mergedInterval)) {
                mergedInterval[1] = Math.max(intervals[i][1], mergedInterval[1]);
                i++;
            }
            res.add(mergedInterval);
        }
        while (i < intervals.length) {
            res.add(intervals[i]);
            i++;
        }
        return res.toArray(int[][]::new);
    }

    private static boolean isOverlap(int[] i1, int[] i2) {
        if (i1[1] >= i2[0] && i1[1] <= i2[1]) {
            return true;
        }
        return i2[1] >= i1[0] && i2[1] <= i1[1];
    }
}