[Softeer/소프티어][level3] 강의실 배정 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=392

Softeer

 

[난이도] level3
[유형] Greedy

[풀이]
강의 종료 시간을 기준으로 정렬하고 0번 강의는 무조건 선택한 뒤,
그 다음 추가가 가능한 강의를 index가 낮은 순서부터 탐색하면서 선택해주면 가장 많은 수의 강의를 추가할 수 있습니다.
현재 선택한 강의의 종료시간보다 다음 강의의 시작시간이 더 늦거나 같으면 선택할 수 있는 강의입니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
pair<int,int> a[1000000];
int N,ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].second,&a[i].first);
    sort(a,a+N);
    for(int i=0;i<N;i++){
        int end = a[i].first;
        ans++;
        bool ok=0;
        for(int j=i+1;j<N;j++){
            if(end<=a[j].second){
                i=j-1;
                ok=1;
                break;
            }
        }
        if(!ok) break;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/강의실_배정.cpp