435. Non-overlapping Intervals / TypeScript

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.

 

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

 

 

풀이

function eraseOverlapIntervals(intervals: number[][]): number {
    let res = 0;
    intervals.sort((x, y)=>x[1] - y[1]);
    let lastEnd = -Infinity;

    for(const interval of intervals){
        const start = interval[0];
        const end = interval[1];

        if(start>=lastEnd){
            lastEnd = end;
        }else{
            res += 1;
        }
    }

    return res;
};

 

중첩되는 구간(intervals)을 제거하여 중첩이 없는 최대한 많은 구간을 남기고, 제거해야 하는 최소 구간의 수를 반환하는 함수

• intervals.sort((x, y) => x[1] - y[1])는 각 구간을 종료 시점 기준으로 오름차순 정렬

 

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

1. 정렬:
   • 종료 시점을 기준으로 오름차순 정렬하면 intervals는 [[1,2], [2,3], [1,3], [3,4]]
2. 구간 순회 및 처리:
   • 초기값:
     • res = 0
     • lastEnd = -Infinity
   • 첫 번째 구간 [1, 2]:
     • start = 1, end = 2
     • start (1) >= lastEnd (-Infinity)이므로 중첩되지 않음.
     • lastEnd를 2로 업데이트.
     • res는 그대로 0.
   • 두 번째 구간 [2, 3]:
     • start = 2, end = 3
     • start (2) >= lastEnd (2)이므로 중첩되지 않음.
     • lastEnd를 3로 업데이트.
     • res는 그대로 0.
   • 세 번째 구간 [1, 3]:
     • start = 1, end = 3
     • start (1) < lastEnd (3)이므로 중첩됨.
     • res를 1로 증가.
   • 네 번째 구간 [3, 4]:
     • start = 3, end = 4
     • start (3) >= lastEnd (3)이므로 중첩되지 않음.
     • lastEnd를 4로 업데이트.
     • res는 그대로 1.

최종적으로, 중첩되는 구간의 수는 res = 1