Accepted and easy to understand Java solution with HashMaps


  • 0
    S

    This solution passed all the test cases on LeetCode. This may not be the best solution out there but definitely a good one to start with and then iterate on it. Does not need any sorting. Uses HashMaps. Please follow comments.

    public int minMeetingRooms(Interval[] intervals) {
    
            if (intervals == null || intervals.length == 0) {
                return 0;
            }
    
            if (intervals.length == 1) {
                return 1;
            }
    
            // how many meetings start at a given time
            Map<Integer, Integer> startToCount = new HashMap<>();
            // how many meetings end at a given time
            Map<Integer, Integer> endToCount = new HashMap<>();
    
            // min of all the meetings start times
            int minStart = intervals[0].start;
            // max of all the meetings end times
            int maxEnd = intervals[0].end;
    
            for (Interval i : intervals) {
    
                if (!startToCount.containsKey(i.start)) {
                    startToCount.put(i.start, 1);
                } else {
                    startToCount.put(i.start, startToCount.get(i.start) + 1);
                }
    
                if (!endToCount.containsKey(i.end)) {
                    endToCount.put(i.end, 1);
                } else {
                    endToCount.put(i.end, endToCount.get(i.end) + 1);
                }
    
                if (i.start < minStart) {
                    minStart = i.start;
                }
    
                if (i.end > maxEnd) {
                    maxEnd = i.end;
                }
            }
    
            int minRooms = 0;
            int rooms = 0;
    
            for (int i = minStart; i <= maxEnd; i++) {
                if (endToCount.containsKey(i)) {
                    // endToCount.get(i) number of meeting rooms were vacated at this time
                    rooms -= endToCount.get(i);  
                }
                if (startToCount.containsKey(i)) {
                    // startToCount.get(i) number of meeting rooms occupied at this time
                    rooms += startToCount.get(i);
                    // record the max of the occupied rooms at any given time.
                    minRooms = Math.max(rooms, minRooms);
                }
            }
    
            return minRooms;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.