Looking at the problem, the O(N) solution is pretty straightforward, and I thought it's for sure going to TLE. Therefore I come up with an O(logN) solution.
From the problem we know:
- "start" of the intervals are sorted
- intervals are not overlapped (i.e. the end of an interval is smaller than the start of next interval, otherwise they are overlapped and should be merged into one)
from the 2 facts we can draw the following conclusion
- "end" of the intervals are also sorted
(proof: For all i, end_i > start_i > end_(i-1) => end_i > end_(i-1). "end" values are sorted)
When you have sorted integer, you can apply binary search and find the place you need to insert. You will need to do it twice: once for start of interval, once for end of interval
- start of interval: last_interval_before_insert.end < newInterval.start
- end of interval: first_interval_after_insert.start > newInterval.end
After you find the start/end of the interval, everything in between should be merged.
The general idea is like that but my code is too ugly so I don't feel like posting them :(
I think this should be a clear example.
def binarySearch(intervals, val): left, right = 0, len(intervals)-1 while left <= right: mid = (left + right) / 2 if intervals[mid].start <= val <= intervals[mid].end: return mid elif val < intervals[mid].start: right = mid - 1 else: left = mid + 1 return left class Solution(object): def insert(self, intervals, newInterval): """ :type intervals: List[Interval] :type newInterval: Interval :rtype: List[Interval] """ if len(intervals) == 0: return [newInterval] left = binarySearch(intervals, newInterval.start) right = binarySearch(intervals, newInterval.end) length = len(intervals) merge_left = left < length and intervals[left].end >= newInterval.start merge_right = right < length and intervals[right].start <= newInterval.end l = left if merge_left or left >= length else left+1 r = right+1 if merge_right else right start = min(intervals[left].start, newInterval.start) if merge_left else newInterval.start end = max(intervals[right].end, newInterval.end) if merge_right else newInterval.end return intervals[:l] + [Interval(start, end)] + intervals[r:]