BOJ 1931 - 회의실 배정

[jusung-c]

문제 : https://www.acmicpc.net/problem/1931
난이도 : 실버 2

---

아이디어

맨 처음에는 회의 목록들을 먼저 시작 시간들을 오름차순으로 정렬 후 시작 시간이 같은 경우 끝나는 시간을 오름차순으로 정렬했다. 정렬 후 이중 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();
    }
}

---

[BanApp]

개꿀잼 그리디 알고리즘,, 이거 끝나는 시간 기준으로 정렬 한다는 아이디어 떠올리는게 생각보다 쉽지 않은데 조건이 될 수 있는 변수들을 따져보면 시작시간, 끝나는 시간, 회의의 길이 이거 3개중에 하나라서 그리디 알고리즘 푸실때는 조건이 될 수 있는 변수들을 먼저 생각해본 다음에 고민해보면 풀수 있을 확률이 높아집니다!

[jusung-c]

오.. 변수가 될 수 있는 후보들을 생각해보는 거 꿀팁이네여