11000번

11000번 - 강의실 배정

처음에 우선순위큐를 쓰는게 좋다는 생각이 들었고, sort 를 하고 시간변수를 선언하는 로직으로 풀면 될 것이라고 생각했다.

그래서 처음에 while문과 for문을 쓰고 time 이란 변수를 1씩 증가시키면서 모든 시간을 체크했는데,

문제에서 시간 제한이 10^9이므로 당연히 시간초과가 발생했다.

그러고 나서는 시간을 1씩 증가시키지 않고, 가장 빨리 시작하는 강의로 넘어가면서 했는데도 시간초과가 발생했다.

while 문과 for문을 써서 시간초과가 발생할 수 밖에 없는 구조였다.

한참을 고민하닥 갓들의 코드를 참고했다...

하지만 생각해보면 while문을 쓰는 이유가, 시간을 앞에서 부터 오름차순으로 증가시키기 위함이었다.

그런데 이미 나는 sort 를 해놓았기 때문에, 따로 while문을 통해서 시간을 증가시킬 필요가 없었다.

그냥 주어진 오름차순된 우선순위큐 값을 이용해서 시간을 넘어가기만 하면 되기 때문이었다.

그러다 보니 while문을 뺀 for문을 이용해서도 문제를 풀 수 있다는 사실을 알게 되었다.

풀고보니 내가 맞은순위에서 2등으로 체크! 처음으로 이런일이!

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, ans = 0;
    cin >> n;
    vector<pair<int, int>> v;
    while (n--)
    {
        int s, e;
        cin >> s >> e;
        v.push_back({ s,e });
    }
    sort(v.begin(), v.end());
 
    priority_queue<int> q;
 
    q.push(-1);
 
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i].first < -q.top())
        {
            q.push(-v[i].second);
        }
        else
        {
            q.pop();
            q.push(-v[i].second);
        }
 
        int size = q.size();
        ans = max(ans, size);
    }
 
    cout << ans << endl;
    return 0;
}