www.acmicpc.net/problem/11000

 

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

+ Recent posts