[정올] 회의실 배정

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=645&sca=50&sfl=wr_hit&stx=1370&sop=and 

JUNGOL

기본적인 그리디 문제입니다. 

 

문제부터 요약하면, 회의를 최대한 안겹치게 개최할 때, 회의 갯수와 어떤 회의들이 개최 되었는지를 출력해야 합니다.

 

<Solution>

회의 종료시간을 기준으로 sorting하여 greedy를 이용하여 구현하면 됩니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int N;
struct meeting{
    int id, start, end;
}meetings[500];

int ids[500];

void getinput(){
    cin >> N;
    for(int i = 0; i<N; i++){
        cin >> meetings[i].id >> meetings[i].start >> meetings[i].end;
    }
}

bool compare(meeting a, meeting b){

    return a.end < b.end;

}

void solution(){
    // sort by endtime
    sort(meetings, meetings+N, compare);

    // initial
    int cnt = 0;
    ids[cnt] = meetings[cnt].id;
    int cur_e = meetings[cnt].end;
    cnt++;

    for(int i =1; i<N; i++){
        if(meetings[i].start <cur_e) continue;

        cur_e = meetings[i].end;
        ids[cnt++] = meetings[i].id;

    }



    // print
    cout << cnt << endl;
    for(int i = 0; i<cnt; i++){
        cout << ids[i] << ' ';
    }
    cout << endl;

}

int main(){
    // get input
    getinput();

    solution();

    return 0;
}