435.Non-overlapping Intervals

My code

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        current = -math.inf
        ans = 0

        for start,end in intervals:
            if start < current:
                ans += 1
            elif end > current:
                current = end
            else:
                ans += 1
        
        return ans

Runtime : 1201ms (beats 83.16%)   
Memory : 55.5MB (beats 10.50%)

풀이

• 끝나는 시간을 기준으로 정렬
• 가장 최근의 interval이 가리키는 것을 current라 저장하기 위해 - infinite로 지정
• 만약 start가 current보다 작으면 제거해야 하는 interval이므로 ans += 1
• end가 current보다 크면 현재의 end를 current로 선언
• 다른 경우에는 ans += 1

greedy search로 풀 계획은 세웠지만, 처음에는 start를 기준으로 정렬을 하고 같은 조건문을 썼었다. 이떄 발생한 문제가, 이 문제에서는 같은 범위의 interval을 짧은 2개의 interval과 긴 interval이 나타내고 있을 때, 적게 제거하기 위해 가장 긴 interval을 제거해야 하는데, start를 기준으로 정렬하면 그 구분을 하기가 어려웠다. 때문에 같은 조건문으로 end를 기준으로 정렬했을 때 조건대로 실행되었다. 또 코드 리뷰를 하면서 알게된 사실인데, 조건문에서 end > current 부분은 end를 기준으로 정렬하고, start가 current보다 크면 반드시 만족하는 조건이기 때문에, 제거하여도 똑같이 실행되었다.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[1])
        current = -math.inf
        ans = 0

        for start,end in intervals:
            if start >= current:
                current = end
            else:
                ans += 1
        
        return ans