57. Insert Intervals

LeetCode

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Solution A

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        int newStart = newInterval[0];
        List<int[]> merged = new ArrayList<>();

        // adds interval into merged list
        // if the start of the interval < the start of the newInterval
        for (int[] interval : intervals) {
            if (interval[0] < newStart) {
                merged.add(interval);
            }
        }

        // adds the newInterval into merged list,
        // merge with the last interval of the list if necessary
        int last = merged.size() - 1;
        if (merged.isEmpty() || merged.get(last)[1] < newInterval[0]) {
            merged.add(newInterval);
        } else {
            int[] lastInterval = merged.get(merged.size() - 1);
            if (lastInterval[1] < newInterval[1]) {
                lastInterval[1] = newInterval[1];
            }
        }

        // adds interval into merged list
        // if the start of the interval >= the start of newInterval
        // merge if necessary
        for (int[] interval : intervals) {
            if (interval[0] >= newStart) {
                int[] lastInterval = merged.get(merged.size() - 1);
                if (lastInterval[1] < interval[0]) {
                    merged.add(interval);
                } else {
                    if (lastInterval[1] < interval[1]) {
                        lastInterval[1] = interval[1];
                    }
                }
            }
        }

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

Solution B

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

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int[] curr = intervals[i];
            if (newInterval == null || curr[1] < newInterval[0]) {
                res.add(curr);
            } else if (newInterval[1] < curr[0]) {
                res.add(newInterval);
                res.add(curr);
                newInterval = null;
            } else {
                newInterval[0] = Math.min(curr[0], newInterval[0]);
                newInterval[1] = Math.max(curr[1], newInterval[1]);
            }
        }
        if (newInterval != null) {
            res.add(newInterval);
        }
        return res.toArray(new int[res.size()][]);
    }
}