11000번: 강의실 배정

 

 

 

 

 

 

풀이

 

자바의 PriorityQueue와 파이썬의 heapq, 우선순위 큐를 사용합니다.

 

오름차 정렬이후에 종료 시간을 시작 시간과 비교합니다.

 

시작 시간이 종료 시간 이상이라면 아래조건을 만족합니다.

(즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

 

1. 정렬된 배열에 첫 번째 종료 시간 값을 큐에 추가 합니다.

 

2. 배열을 두 번째 값부터 순회하면서 queue의 루트 노드 값이 시작 시간 값을 초과한다면 queue에 현재 종료 시간 값을 추가 합니다.

 

3. 아니라면 queue에서 루트 노드 값을 빼고 현재 종료 시간 값을 추가 합니다.

 

4. 마지막으로 queue의 길이를 출력합니다.

 

 

 

 

 

 

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	

		int n = Integer.parseInt(br.readLine());

		StringTokenizer st;
		int[][] timeTable = new int[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			timeTable[i][0] = Integer.parseInt(st.nextToken());
			timeTable[i][1] = Integer.parseInt(st.nextToken());
		} 

		Arrays.sort(timeTable, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {

				if (o1[0] == o2[0])
					return o1[1] - o2[1];

				return o1[0] - o2[0];
			}
		});

		PriorityQueue<Integer> queue = new PriorityQueue<>();
		queue.add(timeTable[0][1]);

		for (int i = 1; i < n; i++) {
			if (queue.peek() > timeTable[i][0])
				queue.add(timeTable[i][1]);

			else {
				queue.poll();
				queue.add(timeTable[i][1]);
			}
		}
		br.close();
		System.out.println(queue.size());
	}	
}

 

 

 

 

 

 

파이썬

import heapq
import sys

n = int(input())

timeTable = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
timeTable.sort(key=lambda x: x[0])

queue = []
heapq.heappush(queue,timeTable[0][1])

for i in range(1,n):
    if queue[0] > timeTable[i][0]:
        heapq.heappush(queue,timeTable[i][1])
    else:
        heapq.heappop(queue)
        heapq.heappush(queue,timeTable[i][1])

print(len(queue))