99클럽 코테 스터디 19일차 TIL (1374번: 강의실)

문제

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

---

학습 키워드

• 그리디
• 정렬
• 우선 순위 큐

 

풀이 및 코드

1. 우선 순위 큐를 사용해서 강의 시간이 가장 적은 순서대로 순회할 수 있도록 저장한다.
2. 강의가 끝나는 시간을 저장하기 위한 강의실 배열을 만든다.
3. 우선 순위 큐와 강의실을 순회하면서 현재 강의의 시작 시간이 진행 중인 강의의 종료 시간보다 작은 경우, 값을 삽입한다. 이때에는 새로운 강의실이 아니라 기존 강의실을 사용하는 것이기 때문에 필요한 강의실의 수는 증가시키지 않는다.
4. 강의가 진행 중인 강의실을 다 돌았는데 강의할 공간이 없다면 새로운 강의실에 강의(의 종료 시간)을 할당한다.

import java.sql.Time;
import java.util.*;
import java.io.*;

class Timeline implements Comparable<Timeline> {
    int courseIndex;
    int start;
    int end;

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

    @Override
    public int compareTo(Timeline o) {
       return this.start - o.start;
    }
}

public class Main {

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

       int N = Integer.parseInt(br.readLine());
       PriorityQueue<Timeline> timelines = new PriorityQueue<>();
       for (int i = 0; i < N; i++) {
          st = new StringTokenizer(br.readLine());
          int courseIndex = Integer.parseInt(st.nextToken());
          int start = Integer.parseInt(st.nextToken());
          int end = Integer.parseInt(st.nextToken());
          timelines.offer(new Timeline(courseIndex, start, end));
       }

       int countOfClassRoom = 0;
       int[] coursesEndTime = new int[100000];
       while (!timelines.isEmpty()) {
          Timeline current = timelines.poll();
          for (int i = 0; i < 100000; i++) {
             if (coursesEndTime[i] == 0) {
                coursesEndTime[i] = current.end;
                countOfClassRoom++;
                break;
             }
             if (coursesEndTime[i] <= current.start) {
                coursesEndTime[i] = current.end;
                break;
             }
          }
       }
       System.out.println(countOfClassRoom);
    }
}