LC435 - Non-overlapping Intervals

Problem

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Solution

Time complexity is $O(n\log n)$. Space complexity is $O(1)$.

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
	intervals.sort()

	res = 0	
	prev = intervals[0][1]

	for start, end in intervals[1:]:
		# not overlapping
		if start >= prev:
			prev = end
			
		# overlapping
		else: 
			res += 1
			prev = min(end, prev)
	return res