[99클럽 5기 코테 스터디 TIL 20일차] 최소 회의실 개수 (feat. 탐욕법(Greedy))

1) 문제

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

2) 풀이

해석 및 코드 설명

1. 입력 처리 및 이벤트 정렬
   • 입력으로 받은 (start, end)를 각각 (start, 1), (end, -1)로 변환하여 리스트에 저장합니다.
   • 정렬 기준:
     • 시간이 다르면 시간 순 정렬 (오름차순)
     • 시간이 같으면 종료(-1)를 먼저 정렬
       → 종료를 먼저 처리해야 동일한 시간에 종료 후 시작하는 경우를 올바르게 처리할 수 있습니다.
2. 스위핑(Sweep) 알고리즘
   • currentRooms(현재 사용 중인 회의실 수) 변수 사용
   • 이벤트 리스트를 순회하면서 currentRooms를 업데이트
   • 최대 회의실 개수를 maxRooms에 저장
3. 최종 결과 출력
   • maxRooms를 출력하면 최소 회의실 개수가 됩니다.

시간 복잡도 분석

• 정렬: O(N log N)
• 스위핑 탐색: O(N)
• 총 시간 복잡도: O(N log N)
  → N이 최대 100,000이므로 충분히 빠르게 동작합니다.

import java.util.*;

public class MeetingRooms {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        List<int[]> events = new ArrayList<>();
        
        // 입력값을 받아 (시간, 타입) 형태로 저장
        for (int i = 0; i < n; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            events.add(new int[]{start, 1});  // 시작 시간은 +1
            events.add(new int[]{end, -1});   // 종료 시간은 -1
        }

        // 정렬: 시간이 같다면 종료(-1)를 먼저 배치
        events.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

        int maxRooms = 0, currentRooms = 0;

        // 스위핑 진행
        for (int[] event : events) {
            currentRooms += event[1];  // 시작이면 +1, 종료면 -1
            maxRooms = Math.max(maxRooms, currentRooms);  // 최대 개수 갱신
        }

        System.out.println(maxRooms);
    }
}