(Interval, Medium) Insert Interval

https://leetcode.com/problems/insert-interval/description/

핵심은 merge 액션이다.
기준값을 계속 갱신해가며 Math.min과 Math.max 활용해서 범위를 넓힌다.

3가지 경우로 나눌 수 있고, 각각에 대해 처리해준다.

1. newInterval보다 왼쪽에 있는 경우
2. merge 대상인 경우
3. newInterval보다 오른쪽에 있는 경우

세 가지 액션을 각각의 while로 볼 수 있다.
모든 액션에서는 i가 1씩 증가하므로 시간복잡도는 O(N)이다. 그 이상의 순회는 없다.

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0];
        int end = newInterval[1];

        List<int[]> list = new ArrayList<>();
        int i = 0;

        while (i < intervals.length && intervals[i][1] < start) {
            list.add(intervals[i]);
            i++;
        }

        while (i < intervals.length && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        list.add(new int[] { start, end });

        while (i < intervals.length) {
            list.add(intervals[i]);
            i++;
        }

        return list.toArray(new int[list.size()][]);
    }
}