11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)
www.acmicpc.net
N개의 수업이 주어지면 강의실을 최소로 사용해서 모든 수업을 해야합니다.
저는 강의 시작시간 기준으로 정렬하였고, 우선순위 큐에 강의 종료시간을 넣었습니다.
q.peek()은 현재 진행중인 강의 중 가장 빠르게끝나는 강의이며, 다음 진행할 강의와 비교를 합니다 (x <= list[i][0])
x <= list[i][0]이면 같은 강의실에서 강의를 할 수 있으므로 remove를 해줍니다.
강의는 무조건 해야하므로 마지막에 끝나는 시간을 add 해줍니다.
마지막으로 q의 크기를 출력하시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][];
static int N;
static void func() {
PriorityQueue<Integer> q = new PriorityQueue<>();
q.add(list[0][1]);
for (int i = 1; i < N; i++) {
int x = q.peek();
if (x <= list[i][0])
q.remove();
q.add(list[i][1]);
}
System.out.println(q.size());
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i][0] = Integer.parseInt(st.nextToken());
list[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] == b[0])
return a[1] - b[1];
else
return a[0] - b[0];
}
});
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 1826 연료 채우기 (0) | 2021.02.22 |
|---|---|
| boj 8980 택배 (0) | 2021.02.16 |
| boj 1931 회의실 배정 (0) | 2021.02.16 |
| boj 2839 설탕 배달 (0) | 2021.02.16 |
| boj 11399 ATM (0) | 2021.01.29 |