[알고리즘] 1931. 회의실 배정

0. 문제

 

1931번: 회의실 배정

 

---

1. 문제 이해

 

1. 그리디 알고리즘 - Activity-Selection Problem

 

---

2. 제출

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ1931 {

    private static class Meeting implements Comparable<Meeting> {
        int start, end;

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

        @Override
        public int compareTo(Meeting o) {
            return this.end == o.end ? Integer.compare(this.start, o.start) : Integer.compare(this.end, o.end);    
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        Meeting[] meetings = new Meeting[N];

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

        Arrays.sort(meetings);

        List<Meeting> list = new ArrayList<>();
        list.add(meetings[0]);
        for(int i=1; i<N; i++) {
            if(meetings[i].start >= list.get(list.size()-1).end) {
                list.add(meetings[i]);
            }
        }

        System.out.println(list.size());
        br.close();
    }

}

• 최대한 많은 회의를 소화하기 위해서는 매 순간 가장 빨리 끝나는 회의를 선택하면 된다.
• return this.end == o.end ? Integer.compare(this.start, o.start) : Integer.compare(this.end, o.end);
  : end를 기준으로 오름차순으로 정렬한다.
• if(meetings[i].start >= list.get(list.size()-1).end) {
  : 회의 시간이 겹치지 않아야 한다.

 

---