CSES 2. Restaurant Customers (1619)

출처: https://cses.fi/problemset/task/1619

---

문제 설명

You are given the arrival and leaving times of n customers in a restaurant.

What was the maximum number of customers?

입력 

The first input line has an integer n: the number of customers.

After this, there are n lines that describe the customers. Each line has two integers a and b: the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

출력

Print one integer: the maximum number of customers.

입력 예

3
5 8
2 4
3 9

출력 예

2

제약조건

• 1 <= n <= 2x10^5
• 1 <= a < b <= 10^9

---

문제 풀이 

입력받은 시간들을 priority queue 에 저장한다.

단, 먼저 도착한 사람이 앞쪽에 나오도록 모두 음수로 만든다.

저장된 queue 의 제일 위쪽에 있는 자료를 확인해서, 도착 시간이면 +1, 떠난 시간이면 -1을 누적한다.

 

이렇게 누적한 손님 수중에서 가장 큰 값을 출력한다.

프로그램 내용

...
    priority_queue<tuple<int, bool>> c_time;

    for(int idx=0; idx < n_Customer; ++idx)
        cin >> start_time >> end_time ;
        c_time.push({-start_time, true});
        c_time.push({-end_time, false});

    int ct_now=0;
    int ct_count=0;

    while (!c_time.empty())
        ct_now += get<1>(c_time.top()) ? 1 : -1; /// start__time +1, end_time -1
        c_time.pop();
        ct_count = max(ct_count, ct_now);

	cout << ct_count << endl;

 

Sorting and Searching ( link )