[BOJ/Greedy] 백준 1931 - 회의실 배정 (Java)

1931 - 회의실 배정

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

 

문제

한 개의 회의실 -> 사용하고자 하는 N개의 회의에 대하여 회의실 사용표
각 회의 I에 대해 시작시간, 끝나는 시간
각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 ㅐㄱ수
(단, 회의는 한 번 시작하면 중간에 중단 X, 한 회의가 끝나는 것과 동시에 다음 회의 시작 O
, 회의의 시작 시간과 끝나는 시간이 같을 수 있음 = 시작하자마자 끝나는 것)

입력
첫째 줄: 회의의 수 N (1 <= N <= 100,000)
둘째 줄 ~ N + 1 줄: 각 회의의 정보 (회의 시작시간, 끝나는 시간)
시작시간, 끝나는 시간 (자연수 or 0) <= 2^{31} - 1
출력: 사용할 수 있는 회의의 최대 개수

---

풀이

• 끝나는 시간이 빠른 회의부터 선택
  • 끝나는 시간 기준으로 오름차순
  • 끝나는 시간이 같으면 시작 시간 오름차순

class Time implements Comparable<Time> {
    public int start, end;

    Time(int start, int end) {
        this.start = start;
        this.end = end;
    }

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

---

코드

import java.io.*;
import java.util.*;

// 회의실 배정
class Time implements Comparable<Time> {
    public int start, end;

    Time(int start, int end) {
        this.start = start;
        this.end = end;
    }

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

public class boj_1931 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Time[] meetings = new Time[N];

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

        Arrays.sort(meetings);

        int cnt = 0;
        int endTime = 0;
        for (int i = 0; i < N; i++) {
            if (meetings[i].start >= endTime) {
                endTime = meetings[i].end;
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}