백준 1931번: 회의실 배정

 

풀이

  유명한 그리디 알고리즘 문제 중 하나다. 회의들의 시작 시간과 끝나는 시간이 주어지면, 회의실 하나로 할 수 있는 최대의 회의 개수를 출력해야 한다.
  문제를 풀기 위해서는 회의들을 끝나는 시간이 빠른 순서대로 재정렬해야 한다. 끝나는 시간이 빠를 수록 다음 회의를 넣을 수 있는 시간대가 커지기 때문이다. 반복문 안에서 차례대로 이전 회의와 시간대가 겹치지 않는지 확인하고, 겹치지 않는다면 회의 개수를 하나씩 늘리도록 한다.

 

코드

#include <iostream>
#include <algorithm>
#define MAX 100020
using namespace std;
typedef struct {
	long long start;
    long long end; 
} meeting; 

bool compare(meeting& a, meeting& b) {
	if (a.end < b.end) {
    	return true;
    }
    else if (a.end == b.end) {
    	return (a.start < b.start);
    } 
    return false; 
} 

int N, answer = 0;
meeting meetings[MAX];

void init() {
	cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0); 
} 

int main() { 
	init(); 
    cin >> N; 
    for (int i = 0; i < N; i++) 
    	cin >> meetings[i].start >> meetings[i].end;
    
    sort(meetings, meetings + N, compare);
    
    answer++;
    int temp = 0;
    for (int i = 1; i < N; i++) {
    	if (meetings[i].start >= meetings[temp].end) {
        	answer++; temp = i; 
        } 
    } 
    cout << answer; 
}