[백준 19598번] 최소 회의실 개수 - java

문제 설명

1. 첫째 줄에 회의의 갯수 N이 주어진다.

2. 그 다음주터 N개의 회의 시작시간 - 끝나는 시간이 주어진다.

3. 그 시간을 통해 모든 회의가 멈추지 않게 작동하는 회의실의 최소 갯수를 구하면 된다.

풀이 과정

 1. (내가 이렇게 풀어서 시간초과가 발생했었는데) 어떤 회의가 언제부터 언제인지를 알 필요는 없다.

 2. 그냥 시작시간부터 회의실 하나의 자리를 차지하고 있고, 뭐가 됐든 나가는 시간에는 나간다는 것이다.

 3. 그러니까 어떤 회의가 언제인지 알 필요는 없고, 언제 입장인지 언제 퇴장인지를 알면 된다.

 4. 그러고 시간 순서대로 나열하면 회의실에 들어가 있는 회의의 갯수를 알 수 있다. 

 

코드

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    List<int[]> rooms = new ArrayList<>();
    int N = sc.nextInt();

    for (int i=0; i<N; i++) {
      int start = sc.nextInt();
      int end = sc.nextInt();

      // 회의실을 잡고있으면 +1, 나가면 -1
      rooms.add(new int[]{start, 1});
      rooms.add(new int[]{end, -1});
    }

    // 그래서 어떤 곳이던 상관 없이 회의가 시작되면 잡고있고, 나가면 방이 하나 빠지는것이다.
    // 누가 나갔는지는 알바 아니고 그냥 잡고 있는 사람들 중 하나 나가면 나갔다고 해주면 된다.
    // 순서대로 정렬하고 들어오고 나가는데 동시에 이루어진다면 나가는게 우선(그래야 새로운 사람이 들어가니까)
    rooms.sort((a, b) -> {
        if (a[0] == b[0]) return a[1] - b[1];
        return a[0] - b[0];
    });
    
    int ans = 0;
    int roomCnt = 0;

    // 방을 잡고 빼면서 그 최대 갯수만 구해주면 된다.
    for(int i=0; i<rooms.size(); i++) {
      int[] nowRoom = rooms.get(i);
      roomCnt += nowRoom[1];
      
      ans = Math.max(ans, roomCnt);
    }
    
    System.out.println(ans);
  }
}