[BOJ/백준][Gold5] 1374 : 강의실 (C++)

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

1374번: 강의실

 

 

[난이도] Gold5
[유형] Greedy

[풀이]
모든 강의의 시작 시간과 종료 시간을 동일한 vector<pair<int,int>>에 저장합니다.
시작 시간의 경우 +1을, 종료 시간은 -1을 묶어서 pair의 second에 저장해줍니다.
그 뒤 시간으로 정렬을 해준 뒤 second를 cur 변수에 더해주면서 이것의 최댓값을 갱신해주면 이것이 정답이 됩니다.
그 이유는 어떤 강의가 시작될때 1을 더해주고 끝날 때 1을 빼주게 되므로
동시에 진행중인 강의의 수가 cur에 저장되게 되기 때문입니다.

 

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct P{
    int s,e;
};
int N,ans;
vector<pair<int,int>> a;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int t,s,e;
        scanf("%d%d%d",&t,&s,&e);
        a.push_back({s,1});
        a.push_back({e,-1});
    }
    sort(a.begin(),a.end());
    int cur=0;
    for(auto [v,m] : a){
        cur+=m;
        ans=max(cur,ans);
    }
    printf("%d",ans);
}

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