[C/C++] #1931 회의실 배정(탐욕)

최대한 많은 회의를 겹치는 시간 없이 하고자 합니다.

 

이 경우에는 빨리 끝나는 회의를 우선 배정하면 다음에 배정할 수 있는 회의가 많아질 수 있습니다.

 

선택의 폭을 넓히기 위해서는 회의가 끝나는 시간순으로 정렬합니다.  그런 후에 현재 끝난 회의의 시간을 기록하고, 시작시간이 그 시간보다 앞이라면 해당 회의는 할 수 없습니다.

 

meeting room

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------
//    baekjoon #1931
//        - by Aubrey Choi
//        - created at 2019-09-07
//------------------------------------------
#include <stdio.h>
#include <algorithm>

struct Lesson { int s, e; };
bool cmp(const Lesson &a, const Lesson &b) { return a.e==b.e?a.s<b.s:a.e<b.e; }
int main()
{
    int n, t=0, ans=0;
    Lesson v[100000];
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d", &v[i].s, &v[i].e);
    std::sort(v, v+n, cmp);
    for(int i=0;i<n;i++)
    {
        if(v[i].s < t) continue;
        t=v[i].e; ans++;
    }
    printf("%d\n", ans);
    return 0;
}