[백준] C++ 1931번 회의실 배정 실버 1 - Greedy Algorithm

문제 : https://www.acmicpc.net/problem/1931
분류 : Greedy Algorithm(그리디 알고리즘)

접근

1. 회의를 시작하는 시간이 빨라도 회의가 늦게 끝나면 최대 회의 수를 구하는 게 어려워진다.
2. 때문에 회의 종료시간에 대해 정렬을 한다.
3. 첫 번째 회의 종료시간(a)과 다음 번 회의 시작 시간(b)을 비교한다.
4. a <= b 여야만 회의가 가능하다.

슈도 코드

input vector(end start)
sort vector

temp = vector[0].first
for 1~N:
  if temp <= v[i].second 
  sum++
  temp = v[i].first

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


void inputMeetings(int N, int start, int end, vector<pair<int, int>> &v){
	for (int i = 0; i < N; i++) {
		cin >> start >> end;
		v.push_back(make_pair(end, start));
	}	
}

int maxMeeting(int N, vector<pair<int, int>> v){
	int temp = v[0].first;
	int sum = 1;
	
	for(int i = 1; i < N; i++) {
		if (temp <= v[i].second) {
			sum++;
			temp = v[i].first;
		}
	}	
	return sum;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N, start, end;
	cin >> N;
	vector<pair<int, int>> v;

	inputMeetings(N, start, end, v);
	sort(v.begin(), v.end());

	cout << maxMeeting(N, v);

	return 0;
}