[백준]강의실 배정(11000)

문제 링크 : [백준]강의실 배정(11000)

문제 설명

N개의 강의가 주어지는데, 각 강의는 시작 시각과 종료 시각이 주어집니다.
같은 시각에 겹치는 강의는 한 강의실에서 진행 할 수 없습니다.
모든 강의를 진행하는데 필요한 최소 강의실 수를 구하세요.

입력

N(강의 갯수, 1 <= N <= 200,000)
S_i E_i(강의 시작, 종료 시각, 1 <= S_i, E_i <= 1,000,000,000)

3
1 3
2 4
3 5

출력

2

카테고리

#이분탐색 #정렬

시간 복잡도 상한

O(N * logN)

해결 방법

1. 특정 강의보다 먼저 시작했으면서 그 강의가 시작할 때까지 종료되지 않은 강의의 갯수를 구하면, 그 강의가 시작할 때 최소 몇개의 강의실이 필요한지 구할 수 있습니다.
2. 1을 구하기 위하여, 시작과 종료 시각을 하나의 구조체로 담아 정렬을 하면 됩니다.
3. 라고 하기엔 하나로 관리를 하게되면, 특정 강의보다 먼저 시작했지만 나중에 끝나는 강의에 대한 갯수를 세는 것이 어려워집니다.
4. 그래서 시작 시각과 종료 시각을 따로 관리합니다.
5. 특정 강의의 시작 시각보다 먼저 종료된 강의는 항상 특정 강의보다 먼저 시작하였기 때문에 갯수를 세는데 문제가 없습니다.
6. 각각을 따로 벡터에 담아 오름차순으로 정렬을 합니다.
7. 특정 강의 시작시각보다 먼저 종료되는 강의의 갯수를 이분탐색으로 파악합니다.
8. 특정 강의의 인덱스가 현재까지 열린 강의의 수가 됩니다.
9. 현재까지 열린 강의의 수 - 종료된 강의의 수를 반복파악합니다.
10. 그 중에서 가장 큰 수를 출력합니다.

시간복잡도

O(N * logN)

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,a,b,i;
vector<int>v,w;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a>>b;
        v.push_back(a);w.push_back(b);
    }
    sort(v.begin(),v.end());
    sort(w.begin(),w.end());
    for(a=i=0;i<n;i++){
        b=upper_bound(w.begin(),w.end(),v[i])-w.begin();
        a=max(a,i+1-b);
    }
    cout<<a;
}