[자료구조] Greedy

[백준 19598] 최소 회의실 개수

ㅋㅋㅋㅋㅋㅋ

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

19598번: 최소 회의실 개수

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
int N;

struct _st
{
	int s, e;
	bool operator<(const _st &v) const {
		if (s == v.s) return e < v.e;
		return s < v.s;	// 시작시간 기준으로 오름차순 정렬 
	}
};

std::priority_queue<int, std::vector<int>, std::greater<int>> PQ;	// 끝나는 시간 오름차순 
std::vector<_st> V;


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int s = 0, e = 0;
		scanf("%d %d", &s, &e);
		V.push_back({ s, e });
	}
}


int get_rooms()
{
	// 초기정보
	std::sort(V.begin(), V.end());
	PQ.push(V[0].e);
	int rooms = 1;

	for (int i = 1; i < N; i++) {
		if (PQ.top() <= V[i].s) PQ.pop();
		else rooms++;
		PQ.push(V[i].e);
	}
	return rooms;
}



int main()
{
	input();
	int ans = get_rooms();
	printf("%d\n", ans);
	return 0;
}

---

[백준 1931] 회의실 배정

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

1931번: 회의실 배정

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
int N;

struct _st
{
	int s, e;
	bool operator<(const _st &v) {
		if (e == v.e) return s < v.s;
		return e < v.e;
	}
};

std::vector<_st> V;

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int s = 0, e = 0;
		scanf("%d %d", &s, &e);
		V.push_back({ s, e });
	}
}

int greedy()
{
	std::sort(V.begin(), V.end());

	int end = V[0].e;
	int conf = 1;
	for (int i = 1; i < V.size(); i++) {
		if (end <= V[i].s) {
			conf++;
			end = V[i].e;
		}
	}
	return conf;
}


int main()
{
	input();
	int ans = greedy();
	printf("%d\n", ans);
	return 0;
}

// PQ로 풀어봤다 
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
int N;
struct _st
{
	int s, e;
	bool operator<(const _st &v) const {
		if (e == v.e) return s < v.s;
		return e < v.e;
	}
};

std::vector<_st> V;
std::priority_queue<int> PQ;


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int s = 0, e = 0;
		scanf("%d %d", &s, &e);
		V.push_back({ s, e });
	}
}

int greedy()
{
	std::sort(V.begin(), V.end());
	PQ.push(V[0].e);

	for (int i = 1; i < V.size(); i++) {
		if (PQ.top() <= V[i].s) {
			PQ.push(V[i].e);
		}
	}
	return PQ.size();
}

int main()
{
	input();
	int ans = greedy();
	printf("%d\n", ans);
	return 0;
}