Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Insert Interval

Problem Statement

Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Example 2:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]]

.....

.....

.....

Like the course? Get enrolled and start learning!
B

brigadirden

· 3 years ago

But since the given list is sorted, we should try to come up with a solution better than O(n log).

This is really confusing - we should try, but in the end nothing said about it and we ending up with time complexity O(n).

Show 2 replies