Simple O(NlgN) Java solution with explanation


  • 1

    Explanation

    The basic idea is referred from StefanPochmann's C++ version: Create a map to store room amount changes for each meeting time point, if it's start time, room + 1; if it's end time, room - 1. Then sort the keys of the map, iterate the room changes, eventually output the maximum room amount as the result.

    Time complexity=O(nlgn) Space complexity=O(n)

    public int minMeetingRooms(Interval[] intervals) {    
            HashMap<Integer, Integer> changes= new HashMap<Integer, Integer>();//Room changes at the specific time.
            for (Interval i : intervals) {
            	Integer start = changes.get(i.start) == null ? 0 : changes.get(i.start);
                changes.put(i.start, start+1);
                
            	Integer end = changes.get(i.end) == null ? 0 : changes.get(i.end);
                changes.put(i.end, end-1);
            }
            int rooms = 0, maxrooms = 0;
            Object array[] = changes.keySet().toArray();
            Arrays.sort(array);
            	       
            for (Object i : array) {
            	rooms += changes.get(i);
                maxrooms = Math.max(maxrooms, rooms);
            }
            return maxrooms;
        }
    

  • 4
    H

    Below code can be avoid if you use TreeMap in java, where key is sorted

        Object array[] = changes.keySet().toArray();
        Arrays.sort(array);
    

    Below is the code with similar algorithm but use TreeMap:

    public int minMeetingRooms(Interval[] intervals) {
        //we must sort the timestamp, otherwise we may incorrectly use offset and skip the max room usage
     	//key is timeStamp, value is num of room that will be occupied start from this moment. 
    	//If a room will be cleared from this moment, then we simply let value--       
        TreeMap<Integer, Integer> hs = new TreeMap<Integer, Integer>();
        
        for(Interval temp : intervals){
            //put timestamp in map
            if(!hs.containsKey(temp.start)) hs.put(temp.start, 0);
            if(!hs.containsKey(temp.end)) hs.put(temp.end, 0);
            
            //based on timestamp to mark the usage of rooms
            hs.put(temp.start, hs.get(temp.start) + 1);//add one room
            hs.put(temp.end, hs.get(temp.end) - 1);//remove one room
        }
        
        int rooms = 0, maxRoom = 0;
        for(int temp : hs.keySet()){
            //update room availability
            rooms += hs.get(temp);
            maxRoom = Math.max(rooms, maxRoom);
        }
        
        return maxRoom;
    }

  • 0

    Thanks a lot, hpplayer, it's really a great idea!


  • 0
    R

    Great idea, but the complexity is still O(nlogn) since each put will cause O(logn) time. Correct me if I am wrong.


Log in to reply
 

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