백준 1931번 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제

입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

출력 1

4

Answer

 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] time = new int[n][2];
        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            time[i][0] = Integer.parseInt(st.nextToken());
            time[i][1] = Integer.parseInt(st.nextToken());
        }

        // sort by end time (in an ascending order)
        Arrays.sort(time, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    // if same end time, sort according to start time
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });

        int count = 0;
        int prevEnd = -1;

        for (int i = 0; i < n; i++) {
            if (prevEnd <= time[i][0]) {
                prevEnd = time[i][1];
                count++;
            }
        }

        System.out.println(count);
    }
}

Notes

• goal: max(# meetings)
• constraints:
  • $\text{meeting i’s start time} \leq \text{meeting i’s end time ( can be equal)}$
  • meetings can’t be stopped. To have meetings, $\text{meeting i’s end time} \leq \text{meeting j’s start time where } i \neq j$
• To have max # of meetings, we need to find non-overlapping meetings that don’t last long and end early - earlier end time.
  • sort the input according to its end time in an ascending order

  • if meetings have the same end time, sort them by their start times in an ascending order(so with (1,2), (2,4) and (4,4), we can have 3 meetings instead of 2 (1,2)(4,4)(2,4))

  • Start from the beginning of the sorted input, count up the meetings with the earliest start times that don’t overlap with the previous meeting’s end time (prev end time <= curr start time)

Reference

The problem is taken from baekjoon