백준 11000 - 강의실 배정(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

정렬을 이용한 그리디 문제입니다.

최소 강의실을 구해야하는 문제입니다.

강의를 최대로 이어서 할 수 있도록 만들어야합니다.

따라서 한 강의를 시작으로 최대한 다른 강의로 이어봅니다.

다른 강의를 시작할 수 없는 때가 온다면 강의실을 하나 추가하고 해당 강의를 시작합니다.

이러한 과정을 반복하면 강의실의 갯수를 구할 수 있습니다.

 

이를 우선순위 큐를 통해서 풀면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int N;
pair<int, int> lec[200001];
priority_queue<int, vector<int>, greater<int>> qu;

bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.first < b.first) return true;
	else if (a.first == b.first) {
		if (a.second < b.second) return true;
		else return false;
	}
	else return false;
}

void solve() {
	sort(lec, lec + N, cmp);
	qu.push(lec[0].second);
	for (int i = 1; i < N; i++) {
		if (qu.top() <= lec[i].first) {
			qu.pop();
			qu.push(lec[i].second);
		}
		else {
			qu.push(lec[i].second);
		}
	}
	cout << qu.size();
}

int main() {
	cin.tie();
	cout.tie();
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		lec[i] = { x,y };
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요