[C++/백준] 11000번: 강의실 배정*

문제 링크

11000번: 강의실 배정

 

풀이

이런 겹치는 구간 문제는 구간의 시작을 1, 끝을 -1로 잡은 다음에 정렬해서 푸는게 베스트인 것 같다.
왜 1과 -1이냐면 겹치는 구간의 개수를 잡기가 편함

1. 강의 시간의 구간을 입력받으면서 v에 구간의 시작은 1, 끝을 -1로 해서 pair로 집어넣는다.
2. v를 정렬하면, 구간의 시간 순으로 정렬될 것이다.
3. 하나씩 살펴보며, 겹치는 구간의 개수인 cnt에 v[i].second를 구해주면 현재 시간에서 겹치는 강의의 개수가 나오게 될 것이다.
   1. 예제를 예로 2번까지 마치면 (1,1), (2,1), (3,-1), (3,1), (4,-1), (5,-1)가 될 것이다.
   2. 앞선 시간에서 강의를 시작했는데 (second가 1인데), 바로 뒤에서도 강의를 또 시작하면 (second가 1이면) 강의가 당연하게 겹치게 될 것이다. 시간 순으로 정렬을 했기 때문에
4. 그래서 모든 강의가 끝날 때까지 살펴보고 최대로 겹치는 강의의 개수를 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++)
    {
        int s, t;
        cin >> s >> t;
        v.push_back({ s,1 });
        v.push_back({ t,-1 });
    }

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

    int answer = 0; // 겹치는 구간의 최대 개수 (답)
    int cnt = 0; // 겹치는 구간의 개수
    for (int i = 0; i < v.size(); i++)
    {
        cnt += v[i].second;
        answer = max(answer, cnt);
    }
    cout << answer;
}