Meeting rooms - rFronteddu/general_wiki GitHub Wiki

Meeting Rooms I

You are given an array of meeting time intervals:

intervals[i] = [start_i, end_i]

Return:

  • true if a person can attend all meetings
  • false if any meetings overlap

Two meetings overlap if:

  • start_j < end_i
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Main {
    static boolean canDo(int[][] m) {
        if(m == null || m.length <= 1) return true;
        Arrays.sort(m, (a,b) -> a[0]-b[0]);
 
        for(int i = 1; i < m.length; i++) {
            if(m[i][0] < m[i-1][1]) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        List<int[][]> testCases = new ArrayList<>();
        List<Boolean> answers = new ArrayList<>();
        
        // Case 1 – overlap
        testCases.add(new int[][]{{0,30},{5,10},{15,20}});
        answers.add(false);
        
        // Case 2 – no overlap
        testCases.add(new int[][]{{7,10},{2,4}});
        answers.add(true);
        
        // Case 3 – touching boundaries
        testCases.add(new int[][]{{1,5},{5,10},{10,15}});
        answers.add(true);
        
        // Case 4 – full overlap
        testCases.add(new int[][]{{1,10},{2,9},{3,8}});
        answers.add(false);
        
        // Case 5 – random order but no overlap
        testCases.add(new int[][]{{10,12},{1,5},{6,9}});
        answers.add(true);
        
        // Case 6 – same start time
        testCases.add(new int[][]{{1,4},{1,3}});
        answers.add(false);
        
        // Case 7 – single meeting
        testCases.add(new int[][]{{5,8}});
        answers.add(true);
        
        // Case 8 – complex overlap
        testCases.add(new int[][]{{4,9},{4,17},{9,10}});
        answers.add(false);
        
        // Case 9 – nested intervals
        testCases.add(new int[][]{{1,100},{11,22},{23,30}});
        answers.add(false);
        
        // Case 10 – empty (edge case)
        testCases.add(new int[][]{});
        answers.add(true);
        
        for(int i = 0; i < testCases.size(); i++) {
            boolean b = canDo(testCases.get(i));
            boolean answ = answers.get(i);
            System.out.println(i++ + " " + b + " " + answ);
        }

    }
}

Meeting Rooms II

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 take place without conflict.

Two meetings conflict if their time intervals overlap.

You may assume:

  • 1 <= intervals.length <= 10^4
  • 0 <= start_i < end_i <= 10^6

Meetings that end exactly when another begins do NOT overlap.

Example: [1, 3], [3, 5] These can use the same room.

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

class Main {
    static int minRooms(int[][] meetings) { 
        if(meetings.length == 0) return 0;

        // sort by start
        Arrays.sort(meetings, (a, b) -> a[0]-b[0]);
  
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(meetings[0][1]);
        
        for (int i = 1; i < meetings.length; i++) {
            if(pq.peek() <= meetings[i][0]) {
                pq.poll();
            }
            pq.add (meetings[i][1]);
        }
        
        return pq.size();
    }
    
    public static void main(String[] args) {
        List<int[][]> testCases = new ArrayList<>();
        List<Integer> answers = new ArrayList<>();
        testCases.add(new int[][]{ {0,30},{5,10},{15,20}});
        answers.add(2);
        
        testCases.add(new int[][]{ {7,10},{2,4}});
        answers.add(1);

        testCases.add(new int[][]{{1,5},{5,10},{10,15}});
        answers.add(1);

        testCases.add(new int[][]{ {1,10},{2,9},{3,8},{4, 7}});
        answers.add(4);
        
        testCases.add(new int[][]{{1,4},{2,5},{7,9},{3,6}});
        answers.add(3);

        testCases.add(new int[][]{{5,8}});
        answers.add(1);
        
        testCases.add(new int[][]{{1,4},{1,3},{1,2}});
        answers.add(3);
        testCases.add(new int[][]{{0,3},{1,5},{4,7}});
        answers.add(2);

       testCases.add(new int[][]{{1,10},{2,7},{3,19},{8,12},{10,20},{11,30}});
       answers.add(4);


        for(int i = 0; i < testCases.size(); i++) {
            int result = minRooms(testCases.get(i));
            System.out.println(result + " expected: " + answers.get(i) + " " + (result == answers.get(i)));
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️