[백준/BOJ] 11000. 강의실 배정 [Gold 5]

11000. 강의실 배정

문제출처 : https://www.acmicpc.net/problem/11000

code

#include <iostream>
using namespace std;

void SelectionSort(int A[], int B[], int n)
{
	int i, j, MinIndex, temp;
	for (i = 0; i < n - 1; i++)
	{
		MinIndex = i;
		for (j = MinIndex + 1; j < n; j++)
			if (A[MinIndex] > A[j])
				MinIndex = j;
		if (MinIndex != i)
		{
			temp = A[i];
			A[i] = A[MinIndex];
			A[MinIndex] = temp;

			temp = B[i];
			B[i] = B[MinIndex];
			B[MinIndex] = temp;
		}
	}
}
int Si[200000] = {}, Ti[200000] = {};
int main()
{
	int N, i, start = 0, end = 0, cnt = 0, flag = 1;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> Si[i] >> Ti[i];

	SelectionSort(Si, Ti, N);

	start = Si[0], end = Ti[0];
	Si[0] = 0, Ti[0] = 0;

	while(flag)
	{
		flag = 0;
		for (int i = 1; i < N; i++)
			if (Si[i] != 0 && end <= Si[i])
			{
				end = Ti[i], Si[i] = 0, Ti[i] = 0;
			}

		for (int i = 0; i < N; i++)
			if (Si[i] != 0)
			{
				start = Si[i]; Si[i] = 0;
				end = Ti[i]; Ti[i] = 0;
				flag = 1;
			}

		cnt++;
	}

	cout << cnt;

	return 0;
}

올해 까지 골드 5를 찍기로 했는데, 드디어 골드를 찍었다. 기분이 너무좋아서 골드5짜리 문제를 보는데, 역시 어려운것 같다....ㅠㅠ

푸는 방법은 맞는것 같은데, 정렬알고리즘 시간복잡도에서 시간초과가 나는것 같다.

나는 수업 시작기준으로 정렬을 하고싶은데 두 배열을 동시에 퀵 정렬하는 방법을 잘모르겠다 ㅠㅠ

수정 2022.03.04

code

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

vector<pair<int, int>>ST;
priority_queue<int> pq;
int main()
{
	int x,y,N, result = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> x >> y;
		ST.push_back({ x,y });
	}

	sort(ST.begin(), ST.end());

	pq.push(-ST[0].second);
	result++;
	for (int i = 1; i < N; i++)
	{
		if (ST[i].first >= abs(pq.top()))
		{
			pq.pop();
			pq.push(-ST[i].second);
		}
		else
		{
			pq.push(-ST[i].second);
		}
		if (result < pq.size())
		result = pq.size();
	}

	cout << result;

	return 0;
}

우선순위 큐를 이용하니까 엄청 쉽게풀렸다.
그때 당시에 못풀던것도 나중에 다시보니까 쉽게풀리는 경우가 있는데, 다시 풀어보니까 정말 쉬운 문제였던것 같다.