8019 : 영화 감독
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$편의 영화가 있으며, 각 영화 $i$의 상영 시간은 $[a_i, b_i]$ 구간입니다.
당신은 한 번에 최대 한 편의 영화만 볼 수 있으며, 한 영화가 끝남과 동시에 다음 영화를 시작할 수 있습니다. (즉, 이전 영화의 종료 시각 $\le$ 다음 영화의 시작 시각)
볼 수 있는 영화의 최대 편수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le a_i < b_i \le 10^9$
당신은 한 번에 최대 한 편의 영화만 볼 수 있으며, 한 영화가 끝남과 동시에 다음 영화를 시작할 수 있습니다. (즉, 이전 영화의 종료 시각 $\le$ 다음 영화의 시작 시각)
볼 수 있는 영화의 최대 편수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le a_i < b_i \le 10^9$
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
다음 $N$개의 줄에 걸쳐 각 영화의 시작 시간 $a_i$와 종료 시간 $b_i$가 공백으로 구분되어 주어집니다.
다음 $N$개의 줄에 걸쳐 각 영화의 시작 시간 $a_i$와 종료 시간 $b_i$가 공백으로 구분되어 주어집니다.
출력 설명
관람할 수 있는 영화의 최대 편수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
3 5
4 9
5 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
구간 스케줄링(Interval Scheduling) 그리디 알고리즘을 사용합니다.
영화들을 종료 시간($b_i$) 기준 오름차순으로 정렬한 뒤, 앞선 영화의 종료 시간 이후에 시작하는 영화를 차례대로 선택해 나갑니다.
영화들을 종료 시간($b_i$) 기준 오름차순으로 정렬한 뒤, 앞선 영화의 종료 시간 이후에 시작하는 영화를 차례대로 선택해 나갑니다.