# 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.

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]]

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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;
while(index < n && start > intervals[index][1]) {
}

//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;

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