공부한 것
- LeetCode #435. Non-overlapping IntervalsNon-overlapping Intervals - LeetCodeCan you solve this real interview question? Non-overlapping Intervals - 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
https://leetcode.com/problems/non-overlapping-intervals/description/
- 방법 2(포기): 시작점 기준으로 오름차순 정렬한 후에, 인접한 두 인터벌이 겹치면 둘 중 길이가 더 긴 쪽을 삭제하는 식으로 전체 인터벌을 순회하는 방법. 두 인터벌이 겹치는데 두 길이가 같으면 둘 중 더 뒤쪽에 있는 인터벌을 삭제한다. ⇒ 다음 경우와 같이 이미 삭제하고 지나친 인터벌이 나중에 필요해지는 경우가 생긴다.
- 방법 3(성공): 끝점 기준으로 오름차순 정렬하고 첫 인터벌을 선택한 후, 그 다음부터 '이전 인터벌의 끝'과 겹치지 않는 가장 가까운 인터벌을 찾아 선택하기를 반복한다. 마지막에는 총 인터벌 개수에서 선택한 인터벌 수를 뺀 값을 반환하면 된다.
방법 3 코드:
// Time Complexity: O(n log n) // Space Complexity: O(log n) function eraseOverlapIntervals(intervals: number[][]): number { if (intervals.length === 1) return 0; intervals.sort((a, b) => a[1] - b[1]); let end = intervals[0][1]; // 정렬 후 첫 인터벌은 선택하고 시작 let count = 1; // result[]에 넣는 대신 숫자로 셈(=제거하지 않는 인터벌의 수 = '선택'한 인터벌의 수) for (let i = 1; i < intervals.length; i++) { const currentStart = intervals[i][0]; // 현재 인터벌이 이전 인터벌과 겹치지 안으면 현재 인터벌을 (제거하지 않는 것으로) '선택'한다. if (currentStart >= end) { // '선택': count를 1 늘이고 end를 업데이트함 count++; end = intervals[i][1]; } } // 전체 인터벌에서 제거하지 않는 총 인터벌 수를 빼 반환한다. return intervals.length - count; }
- 방법 2(포기): 시작점 기준으로 오름차순 정렬한 후에, 인접한 두 인터벌이 겹치면 둘 중 길이가 더 긴 쪽을 삭제하는 식으로 전체 인터벌을 순회하는 방법. 두 인터벌이 겹치는데 두 길이가 같으면 둘 중 더 뒤쪽에 있는 인터벌을 삭제한다. ⇒ 다음 경우와 같이 이미 삭제하고 지나친 인터벌이 나중에 필요해지는 경우가 생긴다.
Uploaded by N2T