# Python greedy solution with explanation

• 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
``````

• 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
``````

• @ahendy Looks nicer. Thank you!

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