57. Insert Interval

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> leftIntervals = new ArrayList<>();
        List<int[]> rightIntervals = new ArrayList<>();

        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];

            if (end < newStart) {
                leftIntervals.add(intervals[i]);
            } else if (newEnd < start) {
                rightIntervals.add(intervals[i]);
            } else {
                newStart = Math.min(start, newStart);
                newEnd = Math.max(end, newEnd);
            }
        }
        
        int[] mergedInterval = new int[]{newStart, newEnd};
        int[][] mergedIntervals = new int[leftIntervals.size() + rightIntervals.size() + 1][2];
        for (int i = 0; i < leftIntervals.size(); i++) {
            mergedIntervals[i] = leftIntervals.get(i);
        }
        mergedIntervals[leftIntervals.size()] = mergedInterval;
        for (int j = 0; j < rightIntervals.size(); j++) {
            mergedIntervals[leftIntervals.size() + j + 1] = rightIntervals.get(j);
        }
        return mergedIntervals;
    }
}