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 -
"""
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
"""
My initial approach - insert the newInterval at a position such that the intervals array remain sorted by start of each interval.
After I have inserted the newInterval, I can merge all the intervals wherever possible.
Solution
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if len(intervals) == 0:
return [newInterval]
intervals.append(newInterval)
intervals = sorted(intervals, key = lambda x : x[0])
# now merge the intervals
i = 1
while i < len(intervals):
p_i = intervals[i-1]
c_i = intervals[i]
if p_i[0] <= c_i[0] and c_i[0] <= p_i[-1]:
intervals[i-1] = [p_i[0], max(c_i[-1], p_i[-1])]
del intervals[i]
else:
i += 1
return intervals
TC - O(nlogn + n^2) because of sorting and deletion.
How can we optimise it ??
We can use binary search to determine the index.
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if len(intervals) == 0:
return [newInterval]
intervals.append(newInterval)
intervals = sorted(intervals, key = lambda x : x[0])
lo = 0
hi = len(intervals) - 1
idx = 0
while lo < hi:
mid = (lo + hi)//2
if intervals[mid][0] <= newInterval[0]:
idx = max(idx, mid)
lo = mid + 1
else:
hi = mid - 1
intervals.insert(idx + 1, newInterval)
# now merge the intervals
i = 1
while i < len(intervals):
p_i = intervals[i-1]
c_i = intervals[i]
if p_i[0] <= c_i[0] and c_i[0] <= p_i[-1]:
intervals[i-1] = [p_i[0], max(c_i[-1], p_i[-1])]
del intervals[i]
else:
i += 1
return intervals
Top comments (0)