[백준][C++] 11000: 강의실 배정(greedy)

문제

11000: 강의실 배정

풀이

• 이 문제는 그리디 알고리즘의 기초 문제인 회의실 배정 문제의 변형이다.
• 이 문제는 최소의 넓이를 구하는 문제이다.
• 여기서 넓이란, 사용하는 강의실의 개수를 말한다.

최소 강의실 개수

• 강의실 개수가 최소이려면?
• 최대한 빽빽하게 시간을 잡으면된다.
• 즉, 강의 사이의 끝시간과 시작시간이 짧으면된다.

정렬

• 시작과 끝을 짧게 만들기 위해서는 일단, 앞에서부터 차근차근 배정하는것이 좋다.

• 그러므로 시작시간을 기준으로 정렬을 했다.

자료구조

• 정렬된 리스트에서, 우리는 짧게 얇게 시간표를 만들어야한다.

• 그러기 위해서 따로 강의실 자료구조를 만들어 처리하는게 좋다.

• 그다음 하나하나씩 가져와 강의실 중 가장 빨리 끝나는 강의실 뒤에 강의를 넣는것이다.

  • 이렇게하면 한 강의실에 최대한 많은 강의를 넣을 수 있다.
  • 한 강의실에 최대한 많은 강의를 넣게되면 사용하는 강의실 개수 또한 최소화된다는 것 또한 생각해보면 알 수 있다.

• 그러므로 자동으로 정렬하는 자료구조인 map, set, priority queu 등을 사용해야한다.

증명?

• 이게 잘 작동할까?

• 시작시간을 기준으로 정렬했다.

• 그리고 순서대로 자료구조에 집어넣었다.

• 그리고 가장 빨리 끝나는 강의실 뒤에 이어 붙였다.

• 이 때 사실 가장 빨리 끝나는 강의실이 아니더라도 이어 붙일 수 있는 아무 강의실이나 이어 붙여도 된다.

  • 이후의 강의들은 시작시간이 더 나중이기 때문에 현재 고민 중인 강의실은 전부 선택할 수 있기 때문이다.

    만약 끝 시각을 기준으로 정렬하게되면, 이게 망가진다. 이후의 강의들의 시작시간이 더 앞서있어서 못 이어붙일 수 있게되기 때문이다.

  • 그러므로 사실 아무 강의실에다 집어넣을 수 있지만 가장 빨리 끝나는 곳에 넣게되면, 그리디 문제에서 흔히 말하는 손해는 없기 때문에, 이는 잘 작동하는 것이다.

코드

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    vector<pair<int, int>> vp(T);

    for (int i = 0; i < T; i++)
    {
        cin >> vp[i].first >> vp[i].second;
    }

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

    priority_queue<int> pq;
    int ans = 1;

    pq.push(-vp[0].second);
    for (int i = 1; i < vp.size(); i++)
    {
        if(-pq.top() <= vp[i].first)
        {
            pq.pop();
        }
        pq.push(-vp[i].second);
    }
    cout << pq.size();
}

반성

• 처음에 map을 사용하여 문제를 해결하려고 했다.
  • map을 사용할 때, 중복된것을 처리해야하는데, 그렇지 않고 size() 를 답으로 제출하니 계속 틀렸었다.
  • 무엇을 답으로 내야하는지 잊어버린것이다.
  • map을 사용하려면 map에 추가할 때 소수점 자리수를 추가하여 전부 다른 값이 오도록하거나, 키를 적절히 제거한 후 second 값들을 전부 더해야한다.