[백준 1931] 회의실 배정

문제링크 : https://www.acmicpc.net/problem/1931

💻 문제 풀이 : C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Room {
	int s_time;
	int e_time;
};

int my_max(int a, int b)
{
	return a > b ? a : b;
}

//bool cmp(Room a, Room b)
//{
//	if (a.e_time < b.e_time) return true;
//	if (a.e_time > b.e_time) return false;
//	if (a.s_time < b.s_time) return true;
//	if (a.s_time > b.e_time) return false;
//	return false;
//}

bool operator<(Room a, Room b)
{
	if (a.e_time > b.e_time) return true;
	if (a.e_time < b.e_time) return false;
	if (a.s_time > b.s_time) return true;
	if (a.s_time < b.s_time) return false;
	return false;
}

int main()
{
	int N;
	cin >> N;

	// vector<Room> v_room;
	priority_queue<Room> q_room;
	vector<Room> now_room;

	for (int i = 0; i < N; i++)
	{
		int st, et;
		cin >> st >> et;
		q_room.push({ st, et });
	}

	for (int i = 0; i < N; i++)
	{
		// 1. 비어있으면 푸쉬
		// if (now_room.size() == 0)
		if (i == 0)
		{
			now_room.push_back( q_room.top() );
		}
		// 2. end_time, start_time 비교
		else if(now_room.back().e_time <= q_room.top().s_time )
		{
			now_room.push_back( q_room.top() );
		}
		q_room.pop();
	}

	/* priority queue Debugging */
	//for (int i = 0; i < N; i++)
	//{
	//	cout << v_room.top().s_time << " " << v_room.top().e_time;
	//	v_room.pop();
	//	cout << endl;
	//}

	int debug = 1;

	cout << now_room.size() << endl;

	return 0;
}

💻 문제 풀이 : Python

list로 풀기

import sys

N = int(input())
room = []

for i in range(N):
    st, et = map(int, input().split())
    room.append([st, et])

# room.sort(key = lambda x: x[0])
# room.sort(key = lambda x: x[1])
room = sorted(room, key = lambda x : (x[1], x[0]))

answer = 1

# now_st = room[0][0]
now_et = room[0][1]

for i in range(1, N):
    if now_et <= room[i][0]:
        # now_st = room[i][0]
        now_et = room[i][1]
        answer += 1

print(answer)

Priority Queue (heapQ)로 풀기

import sys
import heapq

N = int(input())

heapQ = []
for _ in range(N):
    st, et = map(int, input().split())
    heapq.heappush(heapQ, (et, st))

answer = 0

while heapQ:
    now = heapq.heappop(heapQ)
    answer += 1
    if not heapQ:
        break
    while heapQ and heapQ[0][1] < now[0]:
        heapq.heappop(heapQ)
print(answer)

---

📌 memo

😊 C++

Priority Queue

/* 구조체 간의 operator 연산자 비교를 정의해야함!! */
/* 부호를 반대로 해야 의도대로 정렬되는듯...?? */
bool operator<(Room a, Room b)
{
	if (a.e_time > b.e_time) return true;
	if (a.e_time < b.e_time) return false;
	if (a.s_time > b.s_time) return true;
	if (a.s_time < b.e_time) return false;
	return false;
}

	priority_queue<Room> q_room;

	/* priority queue Debugging */
	//for (int i = 0; i < N; i++)
	//{
	//	cout << v_room.top().s_time << " " << v_room.top().e_time;
	//	v_room.pop();
	//	cout << endl;
	//}

priority queue 대신 vector 활용하기!

bool cmp(Room a, Room b)
{
	if (a.e_time < b.e_time) return true;
	if (a.e_time > b.e_time) return false;
	if (a.s_time < b.s_time) return true;
	if (a.s_time > b.e_time) return false;
	return false;
}

	vector<Room> v_room;

	sort(v_room.begin(), v_room.end(), cmp);

😊 Python

lambda로 sort하기

# room.sort(key = lambda x: x[0])
# room.sort(key = lambda x: x[1])
room = sorted (room, key = lambda x : (x[1], x[0]))

heapQ

import heapq

heap = []

heapq.heappush(list, (key1, key2, ...))
heapq.heappop()

---

Ref)
https://gorokke.tistory.com/38
https://vividswan.tistory.com/entry/BOJ-%ED%9A%8C%EC%9D%98%EC%8B%A4%EB%B0%B0%EC%A0%951931