[백준 1931] 회의실배정

문제 링크 : https://www.acmicpc.net/problem/1931

1931번: 회의실배정

기본적인 틀은 시작시간이 빠른 회의 순서대로 정렬하고 하나씩 보면서 회의를 선택하는 방법이다.

 

여기서 회의를 선택할 때 고려해야 되는 부분이 두가지 있다.

 

1. 새로운 회의는 전에 회의가 끝났던 시간보다 늦게 시작해야된다.

 

2. 1의 규칙을 위반하지 않는 회의들 중 가장 빨리 끝나는 회의를 다음 회의로 선택한다.

(시작하는 시간 상관 없이)

 

---

 

#include <iostream>
#include <algorithm>
#define n_ 100005
using namespace std;


struct node{
	int s, e;
};

bool operator<(node a, node b){
	return a.s < b.s;
}

int n;
node arr[n_];

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		arr[i].s = a, arr[i].e = b;
	}
	sort(arr, arr + n);

	int fin = 0;
	int res = 0;
	for (int i = 0; i < n; i++){
		if (arr[i].s >= fin){
			res++;
			fin = arr[i].e;
			continue;
		}

		if (arr[i].e < fin){
			fin = arr[i].e;
			continue;
		}
	}
	cout << res << endl;
}