3) 백준 1931 - 회의실 배정

<문제>

https://www.acmicpc.net/problem/1931

1931번: 회의실배정

조금만 생각해보면 할만 했던 문제! 하지만 조금 더 간단하게 만들 수 있을거 같은데..

 

<코드>

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);

	vector<pair<int, int> > meetings;
	int N, start, end;
	cin >> N;
	
	for(int i = 0; i < N; i++) {
		cin >> start >> end;
		meetings.push_back(make_pair(start, end));
	}
	
	sort(meetings.begin(), meetings.end());
	
	start = 0;
	end = 0;
	int cnt = 0;
	
	for(int i = 0; i < N; i++) {
		if(meetings[i].second < end){
			start = meetings[i].first;
			end = meetings[i].second;
		}
		else if(meetings[i].first >= end) {
			start = meetings[i].first;
			end = meetings[i].second;
			cnt++;
		}
	}
	
	cout << cnt;
    
    return 0;
}

vector을 사용해서 시작 시간과 끝나는 시간 두가지를 pair로 정해서 넣는다.

그 후, 시작시간을 기준으로 작은 수 부터 큰 수 순서로sorting해주고, 시작시간이 같을 경우 끝나는 시간을 sorting해준다.

 

먼저 시작하는 회의부터 시작 시간과 끝나는 시간을 기록해 둔다.

for문으로 시간 순서대로 하나하나 비교를 해주는데 이때, 기록된 끝나는 시간이 비교할 끝나는 시간보다 더 클경우에는 시간을 비교하는 시작시간과 끝나는 시간으로 바꿔준다. 그 후 계속 비교해가는데 현재 하고 있는 회의가 끝나면(기록된 끝나는 시간) 새로운 회의가 시작되어야 하므로 새로운 회의의 시작과 끝시간을 새로 기록해주고 카운팅을 하나 늘려준다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

설명 하는 방법이 너무 어렵다 ㅠㅠ

책을 많이 읽어야 하나 ㅜ