BOJ 1931 - 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

---

 

아이디어

 

맨 처음에는 회의 목록들을 먼저 시작 시간들을 오름차순으로 정렬 후 시작 시간이 같은 경우 끝나는 시간을 오름차순으로 정렬했다. 정렬 후 이중 for문으로 최대 회의 수인 경우를 찾았다.

Arrays.sort(confs);

for (int i = 0; i < N; i++) {
	cnt = 1;
	conference pivot = confs[i];

	for (int j = pivot.end; j < N; j++) {
		if (confs[j].start >= pivot.end) {
			cnt += 1;
			pivot = confs[j];
        }
    }

    result = Math.max(result, cnt);
}

 

이렇게 하면 문제는 풀리는데 시간 초과가 났다. N의 최댓값이 100,000인데 이중 for문이라 시간 복잡도가 10의 10승이나 걸리게 된다.

 

고민하다 결국 다른 사람 풀이를 봤다. 시작 시간이 아닌 끝나는 시간을 기준으로 정렬하면 이중 for문 필요 없이 for문 하나로 구할 수 있었다.

 

왜 그런가 가만히 생각해보니.. 끝나는 시간이 제일 빠른것부터 정렬되니까 다른 케이스들 생각할 필요 없이 정렬 후 첫번째 원소가 무조건 포함되는 경우가 최대라는 것을 깨달았다!

 

 

입력이 다음과 같을 때

 

정렬을 하면 

끝나는 시간이 빠른 것부터 안겹치게 선택해나가면 그게 열릴 수 있는 최대의 회의 개수가 된다.

 

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, cnt;
    static conference[] confs;

    static class conference implements Comparable<conference> {

        public int start;
        public int end;


        @Override
        public int compareTo(conference o) {
            if (end == o.end) {
                return start - o.start;
            }
            return end - o.end;
        }
    }


    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        confs = new conference[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            confs[i] = new conference();
            confs[i].start = Integer.parseInt(st.nextToken());
            confs[i].end = Integer.parseInt(st.nextToken());
        }

    }

    static void pro() throws IOException {
        Arrays.sort(confs);

        cnt = 1;
        conference pivot = confs[0];
        for (int i = 1; i < N; i++) {

            if (confs[i].start >= pivot.end) {
//                    bw.write(confs[j].start+" " + confs[j].end+ "\n");

                cnt++;
                pivot = confs[i];
            }
        }
    }

    public static void print() throws IOException {
        for (int i = 0; i < N; i++) {
            bw.write(confs[i].start + " " + confs[i].end + "\n");
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

//        print();

        bw.write(cnt+" ");
        bw.close();
    }
}