1931번 - 회의실 배정

---

✏️ 문제 풀이

1. 어떤 자료형을 사용할 것인가?
2. 동적 or 정적 배열?
3. 우선순위에 따라 데이터 정렬하기
4. 어떻게 탐색을 진행할 것인가?

 

1) 어떤 자료형을 사용할 것인가?

시간의 최댓값은 2의 31-1이다.
int로 표현할 수 있는 범위 내이기 때문에 int를 사용한다.
(int는 2의 31승부터 표현을 못하기 때문에 long long을 사용해야 함)

2) 동적 or 정적 배열?

메모리 제한은 128MB이다.

시작 시간과 끝나는 시간을 2차원 배열로 저장해야 하는데
데이터의 최대 개수는 100,000로 정적 배열을 사용할 경우 배열의 크기는 100,000 X 100,000이다.

100,000 * 100,000 * 4 byte = 400,000,000,000 byte
1MB = 1,048,576 bytes (1024 × 1024)
400,000,000,000 / 1,048,576 = 38,147 MB

약 38GB로 메모리 제한을 초과한다.

따라서 동적 배열을 사용해야 한다.

vector<pair<int, int>> conference;

3) 우선순위에 따라 데이터 정렬하기

1. 끝나는 시간이 빠를수록
2. 시작하는 시간이 빠른 순 (사실 크게 상관은 없을 것 같지만 정렬 경우의 수를 위해 추가함)

sort(conference.begin(), conference.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second < b.second;
});

 

4) 어떻게 탐색을 진행할 것인가?

끝나는 시간이 가장 빠른 회의를 기준으로 탐색을 진행한다.

정렬된 회의 데이터를 기반으로 탐색할 때,
탐색하는 회의의 시작시간이 이전에 선택된 회의의 끝나는 시간과 같거나 클 경우,
해당 회의를 선택한다.

선택된 회의의 개수를 1 증가시키고 다음 회의를 탐색한다.

---

🖥️ 코드

int N; 
vector<pair<int, int>> conference;

int main(void) {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		int start, end;
		scanf("%d %d", &start, &end);
		conference.push_back(make_pair(start, end));
	}

	sort(conference.begin(), conference.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
		if (a.second == b.second) {
			return a.first < b.first;
		}
		return a.second < b.second;
	});

	int result = 1;
	int c = conference[0].second;
	for (int i = 1; i < N; i++) {
		if (conference[i].first >= c) {
			result++;
			c = conference[i].second;
		}
	}

	printf("%d", result);
	return 0;
}