[BOJ/백준][Gold5] 11000 : 강의실 배정 (C++)

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

 

[난이도] Gold5
[유형] 스위핑

[풀이]
1. pair 배열에 {Si+1,-1}, {Ti,1} 로 분할하여 저장한 뒤 오름차순으로 정렬한다.
2. cnt 변수를 선언하고 여기에는 현재 시간에 동시에 진행중인 수업의 개수(필요한 강의실 수)가 저장되게 된다.
3. cnt 변수를 업데이트 하는 방법은 정렬된 배열 a를 0~2N-1 순서로 차례로 순회하면서
second (-1또는 1) 값을 cnt에서 빼준다. Si (시작) 일때는 새로운 강의가 추가되므로 1을 더해주고
Ti 일때는 강의가 끝나느 것이므로 1을 빼주는 것이다. 정렬할 때 Si에 -1을 넣은 것은 오름차순으로 정렬시 Si가 먼저 오게 하기 위함이다.
이런 식으로 순회하면서 cnt를 업데이트할때, cnt가 가장 큰 값이 나오는 순간이 필요한 강의실 수가 가장 많은 순간이고
필요한 최대 강의실 수가 된다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,ans;
pair<int,int> a[400001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        a[i]={s+1,-1};
        a[i+N]={e,1};
    }
    sort(a,a+2*N);

    int cnt=0;
    for(int i=0;i<2*N;i++){
        cnt-=a[i].second;
        ans=max(cnt,ans);
    }
    printf("%d",ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/11000.cpp