#1931 회의실 배정

# 문제

# 입력 및 출력

# 풀이

잘 모르겠어서 미뤄뒀다가 해결했다ㅋㅋ

일단 처음엔 회의 시간이 짧은 순으로 정렬해야한다고 생각해서

int쌍으로 벡터 만들어서 입력값 저장한다음 정렬해서 계산했음

근데 이렇게 하니까 회의실이 빈 시간을 찾기가 너무 어려워지더라

 

그래서 시작시간 순으로 정렬하고 시작시간이 같으면 끝나는 시간이 작은 순서대로 정렬해야하나 싶었는데

이것도 마찬가지로 0 6 때문에 안되는 가정이었음

정렬하면 0 6이 가장 처음으로 오게 되는데 회의시간이 길기 때문에 이렇게 되면 최대 회의 개수를 구할 수가 없음

 

입력순서대로 보면 1 4 선택하고 이시간과 겹치지 않는 시간인 5 7 선택하고 또 이시간과 겹치지 않는 8 11 선택하고 또 이시간과 겹치지 않는 12 14를 선택하면 힌트와 일치하게 됨

입력대로 받으면 되는것같은데 이게 어떤 방식으로 정렬된 것인지 보다가 회의 종료시간을 보고 알았다ㅋㅋ

 

회의 종료 시간 순서대로 정렬하면 이중 반복문 없이 시간 비교를 할 수 있음

그래서 처음 내가 작성한 코드는 아래와 같음

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,int>> arr;
bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) return a.first > b.first;
	else return a.second < b.second;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, s, e, cnt = 1;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s >> e;
		arr.push_back(make_pair(s, e));
	}
	sort(arr.begin(), arr.end(), compare);
	s = arr.front().first;
	e = arr.front().second;
	for (int i = 1; i < n; i++) {
		if (arr.at(i).first >= e || arr.at(i).second <= s) {
			cnt++;
			s = arr.at(i).first;
			e = arr.at(i).second;
		}
	}
	cout << cnt << "\n";
}

그대로 s, e값으로 받아서 pair로 저장하고 종료시간인 e를 기준으로 정렬했음

그리고 겹치지 않는 시간이랑 비교해서 count 해주고 비교할 값인 s, e를 새로 설정해줌

 

근데 다른 사람 코드를 보다가 더 짧게 할 수 있을 것 같아서 고쳐봄

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,int>> arr;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, s, e, cnt = 1;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s >> e;
		arr.push_back(make_pair(e, s));
	}
	sort(arr.begin(), arr.end());
	e = arr.front().first;
	for (int i = 1; i < n; i++) {
		if (e <= arr.at(i).second) {
			cnt++;
			e = arr.at(i).first;
		}
	}
	cout << cnt << "\n";
}

pair를 만들 때 e, s로 넣어서 종료시간이 먼저 오게 쌍을 만듦

이렇게 되면 compare함수를 따로 안만들어도 자동으로 종료시간을 기준으로 정렬됨

 

이미 시간표에 들어간 회의 종료시간보다 현재 확인할 회의의 시작시간이 큰 지만 확인하면 됨

왜냐하면 종료시간을 기준으로 정렬했기 때문에 이미 시간표에 들어간 회의 시작시간보다

현재 확인할 회의의 종료시간이 작을 수가 없기 때문임

(이미 시간표에 들어간 회의 시작시간 <= 이미 시간표에 들어간 회의 종료시간 

이미 시간표에 들어간 회의 종료시간 <= 현재 확인할 회의의 종료시간

 

이렇게 하면 compare함수 없이 정렬도 가능하고 if문 내의 조건도 하나만 작성하면 됨

메모리와 시간은 똑같지만 코드 길이는 줄어들었음ㅋㅋ

처음엔 예제만보고 그냥 정렬없이 하면 되는 줄 알고 그렇게 했다가 틀렸음