10/28 (토) (완료)인터벌이 안 겹치도록 삭제해야 하는 최소 인터벌 개수 TIL

공부한 것

• LeetCode #435. Non-overlapping Intervals

  Non-overlapping Intervals - LeetCode

  Can 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;
      }

Uploaded by N2T