11000번: 강의실 배정
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)
www.acmicpc.net
수업 시작시간과 종료시간이 주어집니다.
이 정보들을 가지고 모든 수업을 진행하는데 최소의 강의실을 사용해야합니다.
저는 우선순위 큐를 이용하였습니다.
일단 수업시간 정보를 2차원배열을 통해 [시작시간][종료시간]으로 저장하였고,
시작 시간 빠른 순, 시작 시간 같으면 종료 시간 빠른 순으로 정렬하였습니다.
큐에는 수업 종료시간만 저장해주면 되고, 큐에 넣은 종료시간과 다음 수업 시작시간을 비교합니다.
종료시간보다 다음 시작시간이 빠르면 같은 강의실을 사용할 수 없으므로 큐에 push합니다.
종료시간보다 다음 시작시간이 같거나 느리면 같은 강의실을 사용할 수 있으므로 큐를 pop하고 다음 종료시간을 push합니다.
이 과정을 반복하여 큐의 크기가 사용중인 강의실이며, 이를 출력하시면 됩니다.
|
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
54
55
56
57
58
59
60
|
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 PriorityQueue<Integer> q = new PriorityQueue<>();
static int list[][];
static int N;
static void func() {
q.add(list[0][1]);
for (int i = 1; i < N; i++) {
int s = list[i][0];
int e = list[i][1];
if (q.peek() <= s) {
q.remove();
q.add(e);
} else
q.add(e);
}
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 -1;
else if (a[0] == b[0]) {
if (a[1] < b[1])
return -1;
else
return 1;
} else
return 1;
}
});
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
그리고.... Arrays.sort로 list배열을 정렬할 때 Comparator을 사용하여 시간 순으로 정렬하고자 하였습니다.
하지만 compare함수 if에 <=라는 기호를 넣으니 런타임에러가 떴습니다... 신기하게도 <로 바꾸니 AC를 받더라고요...
저번에도 이거때문에 시간좀 많이 날렸었는데 참 신기합니다.. 자바....
공부가 좀 더 많이 필요하겠다는 생각이 드는 하루네요..
'algorithm > data-structure' 카테고리의 다른 글
| boj 5397 키로거 (0) | 2021.02.02 |
|---|---|
| boj 10866 덱 (0) | 2021.02.02 |
| boj 1966 프린터 큐 (0) | 2021.02.01 |
| boj 2164 카드2 (0) | 2021.02.01 |
| boj 10845 큐 (0) | 2021.02.01 |