10/27 (금) 인터벌이 안 겹치도록 삭제해야 하는 최소 인터벌 개수 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/

  

  • 방법 1(포기): 인터벌이 어떤 인터벌과 겹치는지 인터벌 각각에 대하여 ‘겹침 목록’을 만든다. 예를 들어 인덱스 0번 인터벌이 1번, 2번, 10번 인덱스의 인터벌과 겹친다면 0과 set(1, 2, 10)을 묶어두는 자료구조를 사용한다. 그 후 가장 겹침이 많은 인터벌을 삭제하고, 연관된 다른 인터벌들에서도 이 인덱스 번호를 전부 삭제한다. 그 다음으로 겹침 수가 많은 인터벌을 삭제하고 연관된 목록에서도 이 인덱스를 삭제하기를 반복해서, 모든 인터벌의 겹침 수가 0이 되면 반복을 중지한다. 남은 인터벌의 개수를 전체 개수에서 뺀 수가 제거한 인터벌의 수가 되며, 이 것을 반환한다.
  • 방법 2(진행중): 시작점 기준으로 오름차순 정렬한 후에, 인접한 두 인터벌이 겹치면 둘 중 길이가 더 긴 쪽을 삭제하는 식으로 전체 인터벌을 순회하는 방법. 두 인터벌이 겹치는데 두 길이가 같으면 둘 중 더 뒤쪽에 있는 인터벌을 삭제한다. ⇒ 규칙에 뭔가 허점이 있지 않을까 했는데 아니나 다를까 에러 케이스에 걸려 파악 중이다.
    • 코드

      function eraseOverlapIntervals(intervals: number[][]): number {
      	// 0. 인터벌이 하나 뿐이면 삭제할 것 없음. 0을 조기 리턴.
      	if (intervals.length === 1) return 0;
      
      	// 1. 정렬
      	intervals.sort((a, b) => a[0] - b[0]);
      
      	// 2. 순회
      	const result = [intervals[0]];
      	for (let i = 1; i < intervals.length; i++) {
      		let pre = result[result.length - 1];
      		let post = intervals[i];
      
      		if (pre[1] > post[0]) { // 두 인터벌이 겹침
      			// pre가 변경되어야 하는 경우: pre 간격이 더 길 때
      			// (post가 '빠져야' 하는 경우라면 그냥 result에 안 넣으면 되므로 아무 조치 x)
      			if (pre[1] - pre[0] > post[1] - post[0]) {
      				// pre를 삭제하고 post를 넣는다. 
      				result.pop();
      				result.push(post);
      			}	
      		}
      		else { // 두 인터벌이 겹치지 않음
      			// 지금 post 넣기
      			result.push(post);
      		}
      	}
      
      	// 3. 반환
      	return intervals.length - result.length;
      };

Uploaded by N2T