수도 코드 과연 필요할까? - 12764번

머릿속으로 생각하고 노트로 끄적여도 도무지 정리가 안 돼서,

수도코드로 썼더니 시간은 좀 걸려도 확실하게 매듭지을 수 있었다. 만세!

 

깔끔한 수도코드는 아니지만, 틀린 부분도 있고

전체적인 흐름은 노트에 적혀 있으니 머리에 비는 부분이 생겨서 코드를 완성할 수 있다.

 

문제였던 부분은 변수 타입을 어떻게 설정하고

무엇을 정렬해야할지였다.

 

1번: 시작 시간에 어떤 변수에다가 집어 넣고 종료 시간이 되면 빼면 되겠다!

2번: 근데 앞자리부터 채워야하네? pq 써서 항상 앞자리를 뽑을 수 있도록 하자

두개가 keypoint이지 않을까.

 

P가 0일 수도 있다는 점 주의하자.

문제의 조건을 항상 정확하게 확인하도록

 

#include <bits/stdc++.h>
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
#define mem(v, e) memset((v), (e), sizeof((v)))
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n;
int timetable[1'000'001];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int ans = 1;
priority_queue<int, vector<int>, greater<int>> c;
int cnt[1'000'001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int p, q;
        cin >> p >> q;
        pq.push({p, q});
    }
    for (int i = 0; i <= 1'000'000; i++) {
        if (pq.top().ft == i) {
            if (c.empty()) c.push(ans++);
            timetable[pq.top().sd] = c.top();
            cnt[c.top()]++;
            pq.pop();
            c.pop();
        }
        if (timetable[i] != 0) c.push(timetable[i]);
    }
    cout << ans - 1 << "\n";
    for (int i = 1; i < ans; i++) {
        cout << cnt[i] << " ";
    }
    // for (int i = 10; i <= 500; i += 10) {
    //     cout << timetable[i] << " ";
    // }
}
/*
6
20 50
10 100
30 120
60 110
80 90
91 200
=>
4
1 2 1 2

6
20 50
10 100
30 120
60 110
80 90
300 500
=>
4
2 2 1 1
*/