Python greedy solution with explanation


  • 7
    W

    Sort the intervals by their start time. If two intervals overlap, the interval with larger end time will be removed so as to have as little impact on subsequent intervals as possible.

    def eraseOverlapIntervals(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: int
            """
            if not intervals: return 0
            intervals.sort(key=lambda x: x.start)  # sort on start time
            currEnd, cnt = intervals[0].end, 0
            for x in intervals[1:]:
                if x.start < currEnd:  # find overlapping interval
                    cnt += 1
                    currEnd = min(currEnd, x.end)  # erase the one with larger end time
                else:
                    currEnd = x.end   # update end time
            return cnt
    

  • 3

    Small, but I think a better way would to be to change intervals to an iterator. This prevents creating a new list when iterating for x in intervals[1:].

    EG:

    def eraseOverlapIntervals(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: int
            """
            if not intervals: return 0
            intervals.sort(key=lambda x: x.start)  # sort on start time
            intervals = iter(intervals)
            currEnd, cnt = next(intervals).end, 0
            for x in intervals:
                if x.start < currEnd:  # find overlapping interval
                    cnt += 1
                    currEnd = min(currEnd, x.end)  # erase the one with larger end time
                else:
                    currEnd = x.end   # update end time
            return cnt
    

  • 0
    W

    @ahendy Looks nicer. Thank you!


Log in to reply
 

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