Meeting Rooms II

Problem

You are given an array of meeting time intervals:

intervals[i] = [start_i, end_i]

Return the minimum number of conference rooms required so that all meetings can be held without overlap.

Two meetings overlap if one starts before another ends. If a meeting ends exactly when another begins, they do not overlap.

Example

Input: [[0,30],[5,10],[15,20]]
Output: 2

Explanation

• Room 1: [0,30]
• Room 2: [5,10], [15,20]

import java.util.*;

public class Main {
    public static void main(String[] args) {

        List<List<int[]>> testCases = new ArrayList<>();
        List<Integer> answers = new ArrayList<>();

        // Test Case 1
        testCases.add(Arrays.asList(
                new int[]{0,30},
                new int[]{5,10},
                new int[]{15,20}
        ));
        answers.add(2);

        // Test Case 2
        testCases.add(Arrays.asList(
                new int[]{7,10},
                new int[]{2,4}
        ));
        answers.add(1);

        // Test Case 3
        testCases.add(Arrays.asList(
                new int[]{1,5},
                new int[]{8,9},
                new int[]{8,9}
        ));
        answers.add(2);

        // Test Case 4
        testCases.add(Arrays.asList(
                new int[]{1,3},
                new int[]{6,8}
        ));
        answers.add(1);

        // Test Case 5
        testCases.add(Arrays.asList(
                new int[]{1,4},
                new int[]{2,5},
                new int[]{7,9}
        ));
        answers.add(2);

        // Test Case 6 - touching meetings (should reuse room)
        testCases.add(Arrays.asList(
                new int[]{1,3},
                new int[]{3,5},
                new int[]{5,7}
        ));
        answers.add(1);
        
        // Test Case 7 - fully overlapping
        testCases.add(Arrays.asList(
                new int[]{1,10},
                new int[]{2,9},
                new int[]{3,8},
                new int[]{4,7}
        ));
        answers.add(4);
        
        // Test Case 8 - partial overlaps
        testCases.add(Arrays.asList(
                new int[]{1,4},
                new int[]{2,6},
                new int[]{4,7},
                new int[]{5,9}
        ));
        answers.add(3);
        
        // Test Case 9 - identical meetings
        testCases.add(Arrays.asList(
                new int[]{2,5},
                new int[]{2,5},
                new int[]{2,5}
        ));
        answers.add(3);
        
        // Test Case 10 - large overlap cluster
        testCases.add(Arrays.asList(
                new int[]{1,4},
                new int[]{2,5},
                new int[]{3,6},
                new int[]{4,7},
                new int[]{5,8}
        ));
        answers.add(3);
        
        // Test Case 11 - sparse meetings
        testCases.add(Arrays.asList(
                new int[]{1,2},
                new int[]{10,11},
                new int[]{20,21}
        ));
        answers.add(1);
        
        // Test Case 12 - start times same
        testCases.add(Arrays.asList(
                new int[]{1,4},
                new int[]{1,3},
                new int[]{1,2}
        ));
        answers.add(3);
        
        // Test Case 13 - end times same
        testCases.add(Arrays.asList(
                new int[]{1,5},
                new int[]{2,5},
                new int[]{3,5}
        ));
        answers.add(3);
        
        // Test Case 14 - complex mix
        testCases.add(Arrays.asList(
                new int[]{0,30},
                new int[]{5,10},
                new int[]{15,20},
                new int[]{25,35},
                new int[]{28,40}
        ));
        answers.add(3);
        
        // Test Case 15 - single meeting
        testCases.add(Arrays.asList(
                new int[]{5,10}
        ));
        answers.add(1);

        for(int i = 0; i < testCases.size(); i++) {
            System.out.print("Experiment " + i + " ");
            solve(testCases.get(i), answers.get(i));
        }
    }

    public static void solve(List<int[]> intervals, int expected) {

        int result = minMeetingRooms(intervals);

        if(result == expected) {
            System.out.println("PASS");
        } else {
            System.out.println("FAIL -> expected " + expected + " got " + result);
        }
    }

    public static int minMeetingRooms(List<int[]> intervals) {
        List<int[]> events = new ArrayList<>();
        for(var el : intervals) {
            events.add(new int[]{el[0], 1});
            events.add(new int[]{el[1], -1});
        }
        events.sort((a,b)-> {
            if(a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[0], b[0]);
        });
        
        int maxCum = 0;
        int cumul = 0;
        for(var el : events) {
            cumul += el[1];
            maxCum = Math.max(cumul, maxCum);
        }
        
        return maxCum;
    }
}