8018 : 식당 손님
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
식당에 $N$명의 손님이 방문합니다. 각 손님 $i$는 식당에 $a_i$ 시간에 도착하여 $b_i$ 시간에 퇴장합니다 ($a_i \le b_i$).
동시에 식당 안에 머무를 수 있는 최대 손님 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le a_i \le b_i \le 10^9$ (모든 손님의 도착 및 퇴장 시간은 서로 다름)
동시에 식당 안에 머무를 수 있는 최대 손님 수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le a_i \le b_i \le 10^9$ (모든 손님의 도착 및 퇴장 시간은 서로 다름)
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
다음 $N$개의 줄에 걸쳐 각 손님의 도착 시간 $a_i$와 퇴장 시간 $b_i$가 공백으로 구분되어 주어집니다.
다음 $N$개의 줄에 걸쳐 각 손님의 도착 시간 $a_i$와 퇴장 시간 $b_i$가 공백으로 구분되어 주어집니다.
출력 설명
임의의 시점에 식당 안에 머무르는 최대 손님 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
5 8
2 4
3 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
스위핑(Sweeping) 기법을 사용합니다.
각 손님의 도착 이벤트 $(a_i, +1)$와 퇴장 이벤트 $(b_i, -1)$를 생성하여 시간 순서대로 정렬한 뒤, 시간을 따라 이동하며 현재 식당 안의 손님 수를 가감하고 최댓값을 갱신합니다.
각 손님의 도착 이벤트 $(a_i, +1)$와 퇴장 이벤트 $(b_i, -1)$를 생성하여 시간 순서대로 정렬한 뒤, 시간을 따라 이동하며 현재 식당 안의 손님 수를 가감하고 최댓값을 갱신합니다.