O(n) one pass clean code & logic


  • 0

    Just scan the intervals, and make sure whether the newInterval or intervals[i] should be considered to be merged, once the newInterval is merged, you don't want to consider it again, so make it's "start" very large.

    Some corner cases:

    1. Empty given list
    2. newInteral never been merged even after the iteration of the intervals

    Here is an elegant way to solve this: append a very large interval at the end of the intervals, and don't forget to get rid of it when returning.

    class Solution(object):
        def insert(self, intervals, newInterval):
            i, ans = 0, []
            intervals.append(Interval(0xffffffff, 0xffffffff))
            while i < len(intervals):
                if intervals[i].start < newInterval.start:
                    interval = intervals[i]
                else:
                    interval, newInterval.start, i = Interval(newInterval.start, newInterval.end), 0xffffffff + 1, i - 1
                if not ans or interval.start > ans[-1].end:
                    ans.append(interval)
                else:
                    ans[-1].end = max(ans[-1].end, interval.end)
                i += 1
            return ans[:-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.