Insert Interval

Problem : You are given an array of non-overlapping intervals...

Solution : Time Complexity: O(n)

JAVA
1//in : given intervals
2//nIn : new interval to insert
3public int[][] insert(int[][] in, int[] nIn) {
4    ArrayList<int[]> al = new ArrayList<>();
5    int i = 0;
6    int n = in.length;
7
8    // Step 1: Add intervals before nIn (no overlap)
9    while (i < n && in[i][1] < nIn[0]) {
10        al.add(in[i]);
11        i++;
12    }
13
14    // Step 2: Merge overlapping intervals
15    int l = nIn[0], r = nIn[1];
16    while (i < n && in[i][0] <= nIn[1]) {
17        l = Math.min(l, in[i][0]);
18        r = Math.max(r, in[i][1]);
19        i++;
20    }
21    al.add(new int[]{l, r});
22
23    // Step 3: Add remaining intervals (no overlap)
24    while (i < n) {
25        al.add(in[i]);
26        i++;
27    }
28
29    // Convert list to array
30    return al.toArray(new int[al.size()][2]);
31}