Simplest greedy approach so far...


  • 2
    A

    Steps:

    1. Sort intervals by end
    2. fix end to be end of first interval and until start of next interval is smaller than this end, keep incrementing the count which means remove all those intervals
    3. once an interval is found with start >= end (end fixed above), update the end with end of this interval
    class Solution(object):
        def eraseOverlapIntervals(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: int
            """
            if not intervals: 
                return 0
            intervals = sorted(intervals, key=lambda x: (x.end,x.start))
            end = intervals[0].end
            j = 1
            cnt = 0
            
            while(j < len(intervals)):
                if intervals[j].start < end:
                    cnt += 1 
                else:
                    end = intervals[j].end
                j += 1
            return cnt
    

  • 0
    S

    great idea. fresh eyes can do wonders!


Log in to reply
 

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