Leetcode 435. Non-overlapping Intervals

https://leetcode.com/problems/non-overlapping-intervals/description/

Non-overlapping Intervals - LeetCode

문제

간격의 정보가 들어있는 배열 intervals가 주어진다. 이 배열의 각 인덱스에는intervals[i] = [start, end]의 정보가 주어진다. 이때 이 간격들이 겹쳐지지 않도록 하기 위해 지워야하는 간격의 최소갯수를 구하시오!

 

코드

class Solution:

    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:

        intervals.sort(key=lambda x: x[1])

        # print(intervals)

        answer = 0

        flag = 0

        for i in range(1, len(intervals)):

            if intervals[flag][1] > intervals[i][0]:

                answer += 1

            else:

                flag = i

        return answer

---

DP문제라 사실 조금 난해했다.(참고했다는 뜻)

 

처음에는 start를 기준으로 정렬을 했었는데 그렇게 해버리면 하나의 간격이 모든 칸을 차지하고 있는 경우 대처할 방법이 존재하지 않았다. 이러한 문제를 깨닫고 end를 기준으로 정렬하니 위의 문제가 해결되어 통과할 수 있었다.

 

위의 코드를 간단하게 설명하면 end를 기준으로 정렬하게 되면 빨리 끝나는 순서대로 정렬되어 최적을 위해 필요한 interval 그렇지 않은 interval을 구분할 수 있게된다.  이 구분은 정렬된 intervals에서 이전의 간격(intervals[i-1][1]) 그리고 현재의 간격(intervals[i][0])를 비교하여 얻을 수 있다. 만약 겹치지 않는다면 flag에 i를 대입하여 위의 구분을 반복하여 진행하게 되는 코드이다.