Insert Interval

This page explains Java solution to problem Insert Interval using Array data structure.

Problem Statement

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.

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

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Solution

package com.vc.hard;

import java.util.*;

class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;

        //Output
        List<int[]> output = new ArrayList<>();

        //Interval to insert
        int start = newInterval[0];
        int end = newInterval[1];

        int index = 0;
        //Adding Non-Overlapping interval
        while(index < n && start > intervals[index][1]) {
            output.add(intervals[index++]);
        }

        //Merging Interval
        int newStart = index < n ? Math.min(intervals[index][0], start) : start;
        while(index < n && end >= intervals[index][0]) index++;
        int newEnd = index - 1 >= 0 ? Math.max(intervals[index - 1][1], end) : end;
        output.add(new int[]{newStart, newEnd});


        //Adding Remaining intervals
        while(index < n) output.add(intervals[index++]);

        int[][] res = new int[output.size()][2];
        for(int i = 0; i < output.size(); i++) res[i] = output.get(i);

        return res;
    }
}

Time Complexity

O(N)
Where N is total number of intervals

Space Complexity

O(N) Where N is total number of intervals