[LeetCode/Python] 453. Non-overlapping Intervals

📌 Problem

[LeetCode] 242. Valid Anagram

📌 Solution

Solution

Idea

• 끝나는 시간 기준으로 정렬한 뒤, 이전 interval의 끝과 비교하며 순회
  Sort intervals by end time and scan once
• 겹치면 제거하고, 겹치지 않으면 기준 end를 갱신
  Remove an interval if it overlaps with the previous one; otherwise update the end

Code

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        cnt = 0

        intervals.sort(key=lambda x: x[1])
        last_end = intervals[0][1]
        
        for start, end in intervals[1:]:
            if start < last_end:
                cnt += 1
            else:
                last_end = end

        return cnt

Complexity

• Time: $O(n \log n)$
  (sorting dominates; the scan is linear)

• Space: $O(1)$
  (no extra space used apart from sorting)