Greedy 예제(5) Overlapping Intervals

예제 ) 최소 몇 개의 구간을 없애야 겹치는 구간이 없을까?

 

 

 

몇 개를 없애야 할지 직관적으로 보이지 않는다. 이런 경우 문제를 뒤집어 보는 것도 좋다.

 

 

몇 개가 겹치는가  → 몇 개가 겹치지 않은가?

 

알고리즘

 

1) 시간이 빠른 순으로 정렬한다. 

 

 

2) 0 부터 시작하여 하나씩 겹치는 구간은 제거한다. 

 

Greedy 접근법 ( 현재를 기준으로 최적의 값을 찾아가는 과정 )

 

현재값 : 0

1은 0과 겹치므로 제거한다.

 

현재값 : 0 → 2

2는 0과 겹치지 않으므로 남는다. 

 

현재값 : 2

3은 2와 겹치므로 제거한다. 

 

현재값 : 2

4는 2와 겹치므로 제거한다. 

 

 

3) 겹치지 않은 구간 2개이다. 총 5개의 구간에서 겹치지 않은 구간 2개를 빼면 겹치는 구간은 3개이다. 

 

 

고로, 최소 3개의 구간을 없애야 겹치는 구간이 사라진다. 

 

 

---

 

참고영상