정올/회의실배정

회의실이 하나 있다. 여러 회의들이 시작시간과 종료시간이 예약되어 있으며, 시간대가 겹치는 회의는 동시에 개최가 불가능하다. 따라서 같은 시간대에 속하는 회의들 중 하나만 개최하고 나머지 회의들은 버려야한다. 

단, 종료시간과 시작시간이 같은 경우에는 시간이 겹친다고 말하지 않는다. 회의의 개수 N과 각 회의의 시작시간, 종료시간이 주어졌을 때 되도록 많은 회의를 개최하고자 한다.

 

회의를 최대한 많이 배정하는 프로그램을 작성하시오.

 

첫줄에는 회의의 수 N(5≤N≤500), 둘째 줄부터 i-1번 회의의 번호와 시작시간과 종료시간이 차례로 주어진다. (500 이하의 자연수)

첫줄에는 배정 가능한 최대의 회의수를 출력하고 다음 줄부터는 배정한 회의의 번호를 시간대순으로 출력한다. 만약, 답이 여러 가지(최대회의수가 될 수 있는 배정 방법이 여러가지)라면 그 중 아무거나 하나 출력한다.

6 1 1 10 2 5 6 3 13 15 4 14 17 5 8 14 6 3 12

3 2 5 4

Code

#include <iostream>

using namespace std;

////macro

#define max 500

typedef class conference{

public:

int number;

int start;

int finish;

/*

conference(int enumber, int estart, int efinish) :number(enumber), start(estart), finish(efinish){

}

*/

}cf;

int main(){

cf con[max];

int loop;

int finish = -1;

int num[500] = { 0, };

int num_count = 0;

cin >> loop;

//회의 번호 입력

for (int i = 0; i < loop; i++){

cin >> con[i].number >> con[i].start >> con[i].finish;

}

//회의 종료 시간에 맞춰서 데이터를 정렬

for (int j = 0; j < loop ; j++){

for (int i = 0; i < loop -1-j; i++){

if (con[i].finish > con[i + 1].finish){

cf temp = con[i];

con[i] = con[i+1];

con[i+1] = temp;

}

}

}

//알고리즘

for (int i = 0; i < loop; i++)

{

if (con[i].start >= con[finish].finish)

{

num[num_count++] = con[i].number;

finish = i;

}

}

//출력

printf("%d\n", num_count);

for (int i = 0; i <= num_count-1; i++){

printf("%d ", num[i]);

}

}