[백준/BOJ] 1374. 강의실 [Gold 5]

1374. 강의실

문제출처 : https://www.acmicpc.net/problem/1374

code

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    int N, num, x, y, cnt = 0, i, index = 0;
    vector<pair<int, int>> arr;
    priority_queue<int> pq;

    cin >> N;
    for (i = 0; i < N; i++)
    {
        cin >> num >> x >> y;
        arr.push_back({ x,y });
    }

    sort(arr.begin(), arr.end());

    pq.push(arr[0].second);

    while (!pq.empty())
    {
        for (i = 1; i < N; i++)
        {
            if (arr[i].first >= pq.top())
            {
                pq.pop();
                pq.push(arr[i].second);
                arr[i].first, arr[i].second = -1;
            }
        }
        pq.pop();
        for (i = 1; i < N; i++)
            if (arr[i].first != -1)
            {
                pq.push(arr[i].second);
                arr[i].first, arr[i].second = -1;
                break;
            }
        cnt++;
    }

    cout << cnt;

    return 0;
}

시간초과

O(N)으로 해결할수 있다는데 아직 잘모르겠다 ㅠㅠ

수정 2022.03.05
code

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

vector<pair<int, int>> arr;
priority_queue<int> pq;
int main()
{
    ios::sync_with_stdio(false);

    int N, i, num, x, y, result = 0;
    cin >> N;

    for (i = 0; i < N; i++)
    {
        cin >> num >> x >> y;
        arr.push_back({ x,y });
    }

    sort(arr.begin(), arr.end());

    pq.push(-arr[0].second);
    result++;

    for (i = 1; i < N; i++)
    {
        if (arr[i].first >= abs(pq.top()))
        {
            pq.pop();
            pq.push(-arr[i].second);
        }
        else
        {
            pq.push(-arr[i].second);
        }
        if (result < pq.size())
            result = pq.size();
    }

    cout << result;

    return 0;
}

어제 다시풀었던 백준 11000번문제 강의실 배정문제랑 메커니즘이 똑같애서 설마 코드가 똑같은데 되겠어? 했는데 복붙하니까 그대로 통과됐다.

우선순위 큐를 이용한 문제였다.