Algorithm : Meeting Arrangement

meeting_arrangement.cpp

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void sort_meetings_order_by_finish(int numberOfMeetings, int **meetings);

int main()
{
	int numberOfMeetings = 0;
	char buf[5];

	std::ifstream fin;
	fin.open("input.txt");
	fin >> numberOfMeetings;

	int **meetings = new int*[numberOfMeetings];
	for (auto i = 0; i < numberOfMeetings; ++i) {
		meetings[i] = new int[3];
		for(auto j = 0; j < 3; j++) {
			fin >> meetings[i][j];
		}
	}
	fin.close();

	sort_meetings_order_by_finish(numberOfMeetings, meetings);

	int firstIndex = meetings[0][0];
	int lastEndTime = meetings[0][2];

	int count = 1;
	std:string result;
	_itoa_s(firstIndex, buf, 10);
	result.append(buf);
	result.append(" ");

	for(auto i = 1 ; i < numberOfMeetings ; ++i){
		int start = meetings[i][1];
		int finish = meetings[i][2];

		if(start >= lastEndTime) {
			lastEndTime = finish;
			count++;
			_itoa_s(meetings[i][0], buf, 10);
			result.append(buf);
			result.append(" ");
		}
	}

	std::ofstream fout;
	fout.open("output.txt");
	fout << count << endl;
	fout << result.c_str();
	fout.close();

	delete[] meetings;

	return 0;
}

void sort_meetings_order_by_finish(int numberOfMeetings, int **meetings) {
	for(auto i = 0; i < numberOfMeetings; ++i){
		for(auto j = 1; j < numberOfMeetings - i; ++j){
			if(meetings[j-1][2] > meetings[j][2]) {
				int *tmp = meetings[j-1];
				meetings[j-1] = meetings[j];
				meetings[j] = tmp;
			}
		}
	}
}

Algorithm: Meeting Arrangement

Condition

• 1 meeting room
• overlapped meetings are not permitted
• end time and next begin time can be overlapped

Objective

• arrange as many as meetings!

Input

1. first line : a number of meetings
2. after that : meeting information (meeting no, meeting begin time, meeting end time)

Output

1. first line : a number of possible meetings
2. second line : possible meeting index that is ordered by time

Example

[Input]

13

1 3 5

2 11 14

3 6 8

4 13 15

5 14 17

6 8 14

7 20 21

8 18 22

9 7 16

10 9 16

11 5 6

12 3 12

13 23 24

[Output]

7

1 11 3 2 5 7 13