# Simple O(NlgN) Java solution with explanation

• 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;
}
``````

• 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;
}``````

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

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

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