[Leetcode 아주 상세한 문제풀이] 435. Non-Overlapping Interval - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 435번 문제 Non-Overlapping Interval 이다.

우선 문제를 살펴보자.

 

리트코드 435번 문제 Non-Overlapping Interval 링크

Non-overlapping Intervals - LeetCode

Non-overlapping Intervals - LeetCode

 

 

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 1:
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.

Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104

 

 

문제 설명

문제에 대해 간략히 설명하면, 시작과 끝 지점으로 이루어진 구간 배열이 주어진다. 이 구간 배열들은 서로 겹칠수도 안겹칠수도 있다. 이때 주어진 구간 배열들이 겹치지 않도록 하기 위해서 제거해야 하는 최소한의 구간 배열 개수를 구하는 문제다.

문제 예시 1번에서 포는 것처럼 4개의 구간 배열이 위와 같이 주어져 있다. 이때 주어진 배열 중 처음 3개의 구간 배열 ([1, 2], [2, 3], [3, 4])은 서로 겹치지 않는다. 따라서 우리는 마지막 구간 배열 [1, 3] 하나만 제거한다면 주어진 배열을 서로 겹치지 않게 할수 있다. 이제 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제에 대한 접근 방식은 여러가지 일 수 있겠지만,

가장 쉽게 접근하는 방법은 우선 주어진 구간 배열을 오름차순으로 배열하는 것이다.

오름차순으로 배열한 후 주어진 구간 배열들을 하나씩 차례대로

바로 그 앞에 위치한 구간 배열들과 비교해 겹치는지 안겹치는지 확인해 보는 것이다.

 

예를 들어 주어진 구간 배열이 [[4,6], [1,3], [2,4]]으로 주어졌을 때

이 구간 배열들을 오름차순으로 배열하게 되면 위 그림과 같이 된다.

오름차순 배열 후 첫번째 구간 배열 [1, 3]과 두번째 구간 배열 [2, 4]를 비교하면

두 배열은 겹치기 때문에 둘 중 하나를 제거하면 된다.

하지만 이 문제는 좀 더 쉬운데, 둘 중 하나를 제거하지 않고

배열들을 겹치지 않게 하기 위해 제거해야 하는 구간 배열 '개수'를 구하는 것이기 때문에 

두 배열이 겹치는 경우마다 카운트를 해주면 된다.

이런 방식으로 모든 구간 배열들을 비교하여

그 배열들이 서로 겹칠때마다 카운트를 해주면 된다.

이제 문제를 풀어보자. 

 

 

문제 풀이

구간 배열을 입력받기 위한 함수를 정의해준다 (line 1)

만약 주어진 구간 배열이 비어있다면 0을 리턴해주고 종료한다. (line 2)

앞서 설명한대로 주어진 구간 배열을 오름차순으로 배열해준다 (line 6)

단, 구간의 '끝'을 기준으로 오름차순 배열한다

우리는 항상 구간 배열의 '끝'을 비교해야 하는데

앞선 예제 [1, 3]과 [2, 4]라는 배열이 주어졌을 때 

[1, 3]의 끝 3과 [2, 4]의 처음 2를 비교해

첫번재 배열의 끝 값이 두번째 배열의 처음 값보다 크면 두 배열은 겹치는 것이기 때문이다.

따라서 구간 배열의 '끝'을 트레킹 하기 위한 변수를 하나 만들어준다 (line 9)

그리고 겹치는 배열이 몇개인지 카운트 하기 위한 변수도 하나 만들어 준다 (line 10)

주어진 구간 배열 개수만큼  for loop를 돌린건데 (line 11)

만약 기존 배열의 '끝'이 그 다음 배열의 '처음' 값보다 크다면 (line 12)

그 두 배열은 서로 겹치는 것이기 때문에 카운트를 해준다 (line 13)

만약 그렇지 않다면 두 배열은 겹치지 않기 때문에 (line 14)

이때는 비교하는 배열의 '끝' 값을 업데이트 해준다 (line 15)

for loop를 모두 돌게 되면 겹치는 배열의 개수가 카운트 되었으므로

그 값은 리턴해주고 종료한다(line 18) 

 

 

문제 풀이 코드

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0
    
    # Step 1: Sort the intervals by their ending times
    intervals.sort(key=lambda x: x[1])
    
    # Step 2: Traverse the sorted intervals
    prev_end = intervals[0][1]
    count_removed = 0
    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:  # Overlapping with previous interval
            count_removed += 1
        else:
            prev_end = intervals[i][1]
    
    # Step 3: Return the count of removed intervals
    return count_removed
 
# Test cases
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # Expected: 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))       # Expected: 2
print(erase_overlap_intervals([[1,2],[2,3]]))             # Expected: 0
 

 

 

관련 문제

리트코드 56번 Merge interval 문제 풀이 (링크)

리트코드 57번 Insert interval 문제 풀이 (링크)

 

435. Non-Overlapping Interval