[Leetcode] 57. Insert Interval

[Problem Link]

https://leetcode.com/problems/insert-interval/

[Difficulty]

Hard

[Problem Description]

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.

Get Yi-Ting Lin’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

[Problem Explanation]

In this problem, we are asked to insert an interval named newInterval in a given set of intervals. Besides, intervals might be merged while inserting newInterval. Note that the range of value of each interval[i] is [interval[i][0], interval[i][1]].

[Think Process]

To begin with, the key to solving this problem is to handle the “merge problem” occurred while the insertion of newInterval. Hence, we could first define the two relationships between nonoverlapping interval[i] and newInterval as following:

1. interval[i] < newInterval → Intervals[i][1] < newInterval[0] 
   (e.g [1,2] < [3,4])
2. interval[i] > newInterval → Intervals[i][0] > newInterval[1]
   (e.g [3,4] > [1,2])

Based on 1. and 2. mentioned above, we could infer that “if interval[i] and newInterval are overlapping, then interval[i] is neither greater nor less than newInterval”. Aside from it, the method to merge two overlapping intervals could be done by as following:

newInterval[0] = min(newInterval[0], Intervals[i][0])
newInterval[1] = max(newInterval[1], Intervals[i][1])

Now, we can start to solve this problem! we can divide intervals[i] into three parts: “interval[i] < newInterval”, “interval[i] and newInterval are overlapping” and “interval[i] < newInterval”. By doing this we are able to focus on the overlapping part where merges of intervals are needed since the only thing we have to do on the other two parts is to add intervals[i] into the result.

[Solution]

[Complexity Analysis]

Time complexity: O(n), where n is the size of the given intervals.

Space complexity: O(1)