(cpp) Softeer ‘강의실 배정’ - 그리디

02 Oct 2022 on Programming Languages

Softeer ‘강의실 배정’ - 그리디

---

문제 백준 1931번 과 같은 풀이사용

풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>

using namespace std;

int n,s,f;
vector<pair<int,int>> table;


int main(int argc, char** argv)
{
	//강의 수 N
	//시작시간s, 종료시간f
	//s[1 3 4]
	//f[1 2 3]
	//첫 강의 : 종료시간 제일 빠른거 
	//그 이후 : 강의 시작 시간이 이전 강의 종료시간과 같거나 큰 것
	//          강의 시작 시간이 같다면 강의 종료시간이 빠른 거
	//--> 강의 종료시간 기준으로 정렬
	//현재시각 = 강의 종료 후 시각
	cin >> n;
	int ret =n;
	while(ret--){
		cin >> s >>f;
		table.push_back(make_pair(f,s));
	}

	sort(table.begin(),table.end());
	
	int cur_time = table[0].first;

	int ans = 1;

	for (int i=1; i<n;i++){
		if(cur_time <= table[i].second){
			cur_time = table[i].first;
			ans = ans +1;
		}
	}
	cout << ans;

	return 0;
}