강의실 - 1374

문제

풀이

package Baekjoon;


import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

// 강의실 - G5 - 그리디,정렬

class Study implements Comparable<Study>{
    int num;
    int st;
    int et;

    public Study(int num,int st, int et){
        this.num = num;
        this.st = st;
        this.et = et;
    }

    @Override
    public int compareTo(Study o) {
        return this.st - o.st;
    }
}

public class ex1374 {

    static int n;
    static int cnt = 0;
    static ArrayList<Study> arr = new ArrayList<>();
    public static void solution(){
        Collections.sort(arr);

        PriorityQueue<Integer> Q = new PriorityQueue<>();
        Q.add(0);

        for(Study x : arr){
            int et = Q.peek();

            if(x.st >= et) Q.poll();
            Q.add(x.et);
        }
        cnt = Q.size();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        for(int i=0; i<n; i++){
            int num = sc.nextInt();
            int st = sc.nextInt();
            int et = sc.nextInt();

            arr.add(new Study(num,st,et));
        }
        solution();
        System.out.println(cnt);
    }
}

처음에 일반 정렬로 문제를 해결하려고 시도.. 해결이 되지않아서 다른 방법을 찾아보니 PriorityQueue를 이용해서 풀어야하는 것 같더라. 이 우선순위 큐는 그냥 선언하면 최솟값을 먼저 출력해주기 때문에 먼저 끝나는 강의 시간과 시작하는 강의의 시간을 비교하기 좋다.

문제 풀이 방식은 Comparable<> 를 인터페이스를 이용해 강의 시작시간을 기준으로 오름차 정렬을 해준다. 그 후에 priorityQueue를 선언해서 먼저 끝나는 강의 시간보다 다음에 시작하는 강의시간이 같거나 더 크면 강의를 빼주고 나머지는 전부 강의실을 추가해주는 방식으로 진행하면 해결이 가능하다.