백준 11000번 : 강의실 배정(자바)

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

---

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

---

출력

강의실의 개수를 출력하라.

💡풀이

입력이 20만개이다. N^2미만의 시간복잡도를 가져가야 한다. 그리디 알고리즘을 사용했는데 입력들의 수업 시작 시간을 기준으로 정렬하였다. 그리고 우선순위 큐를 만들고 끝나는 시간을 기준으로 우선 순위를 부여하였다.  사용하고 있는 강의실중에 가장 빨리 강의실의 시간보다 다음 수업 시작이 느리거나 같다면 같은 강의실을 사용할 수 있기에 큐에서 지운후 넣어준다. 그것이 아니라면 새로운 강의실이 필요하기 때문에 그냥 큐에 넣어준다. 마지막으로 큐의 사이즈를 구하면 최소로 필요한 강의실의 개수가 된다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer;
    int N = Integer.parseInt(br.readLine());
    int[][] arr = new int[N][2];


    for (int i = 0; i < N; i++) {
      stringTokenizer = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(stringTokenizer.nextToken());
      int b = Integer.parseInt(stringTokenizer.nextToken());
      arr[i][0] = a;
      arr[i][1] = b;
    }

    Arrays.sort(arr, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        if (o1[0] == o2[0]) {
          return o1[1] - o2[1];
        }
        return o1[0] - o2[0];
      }
    });

    PriorityQueue<ClassRoom> classRooms = new PriorityQueue<>(Comparator.comparing(ClassRoom::getNum));
    classRooms.add(new ClassRoom(arr[0][1]));

    for (int i = 1; i < N; i++) {
      int a = arr[i][0];
      int b = arr[i][1];

      if (classRooms.peek().getNum() <= a) {
        classRooms.poll();
      }
      classRooms.add(new ClassRoom(b));
    }

    System.out.println(classRooms.size());
  }
  static class ClassRoom{
    int num;

    public ClassRoom(int num){
      this.num = num;
    }
    public int getNum(){
      return num;
    }

  }
}