LeetCode 57. Insert Interval

57. Insert Interval

Difficulty: Hard

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.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

Language: Java

This solution is quite straightforward, and it’s based on the non-overlapping feature.

Use a stack to store all items in intervals, make sure the item that has smaller index on top. And the stack concept can be realized using a real Stack or just use the index (because there is no push action).

Here are next steps:

1. Add all non-overlapping item with newInterval to result
2. While there is overlapping between newInterval and stack top, replace the newInterval with the overlapped result and pop stack. It ends when the stack is empty or there is no overlapping any more (remember, the origin intervals has no overlapping).
3. Add newInterval to result;
4. Add all left items in stack to result.

Using stack, beats 86%

class Solution {
      public int[][] insert(int[][] intervals, int[] newInterval) {
            if (intervals == null) {
                  return intervals;
           }
            Deque<int[]> stack = new ArrayDeque<>();
            for (int i = intervals.length - 1; i >= 0; i--) {
                  stack.push(intervals[i]);
           }
            List<int[]> list = new ArrayList<>();
            while (!stack.isEmpty() && stack.peek()[1] < newInterval[0]) {
                  list.add(stack.pop());
           }
            while (!stack.isEmpty() && isOverlapped(newInterval, stack.peek())) {
                  newInterval = overlap(newInterval, stack.pop());
           }
            list.add(newInterval);
            while (!stack.isEmpty()) {
                  list.add(stack.pop());
           }
            return parseIntervals(list);
     }
      
      private boolean isOverlapped(int[] a, int[] b) {
            return !(a[1] < b[0] || b[1] < a[0]);
     }
      private int[] overlap(int[] a, int[] b) {
            return new int[] {Math.min(a[0], b[0]), Math.max(a[1], b[1])};
     }
      
      private int[][] parseIntervals(List<int[]> intervals) {
            int[][] result = new int[intervals.size()][2];
            for (int i = 0; i < result.length; i++) {
                  result[i] = intervals.get(i);
           }
            return result;
     }
}

Using array index, beats 99.98%

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null) {
            return intervals;
        }
        int index = 0;
        List<int[]> list = new ArrayList<>();
        while (index < intervals.length && intervals[index][1] < newInterval[0]) {
            list.add(intervals[index++]);
        }
        while (index < intervals.length && isOverlapped(newInterval, intervals[index])) {
            newInterval = overlap(newInterval, intervals[index++]);
        }
        list.add(newInterval);
        while (index < intervals.length) {
            list.add(intervals[index++]);
        }
        return parseIntervals(list);
    }
    
    private boolean isOverlapped(int[] a, int[] b) {
        return !(a[1] < b[0] || b[1] < a[0]);
    }
    private int[] overlap(int[] a, int[] b) {
        return new int[] {Math.min(a[0], b[0]), Math.max(a[1], b[1])};
    }
    
    private int[][] parseIntervals(List<int[]> intervals) {
        int[][] result = new int[intervals.size()][2];
        for (int i = 0; i < result.length; i++) {
            result[i] = intervals.get(i);
        }
        return result;
    }
}