How do you solve Meeting Rooms III on LeetCode?

Meeting Rooms III (LeetCode #2402) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Prioritize room assignment based on earliest end times.

What is the brute force solution for Meeting Rooms III?

The brute force approach for Meeting Rooms III is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each meeting against all rooms to find an available one. If no room is available, we delay the meeting until a room becomes free. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Meeting Rooms III?

Always clarify the problem constraints and edge cases. Discuss your thought process and approach before jumping into coding. Test your solution with multiple scenarios to ensure correctness.

What are common mistakes when solving Meeting Rooms III?

Failing to properly manage room availability and delays. Not considering the need to adjust meeting durations when delayed.

#2402

Meeting Rooms III

Hard

ArrayHash TableSortingHeap (Priority Queue)SimulationHeapSimulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

Using two heaps allows us to efficiently manage room availability and meeting scheduling. One heap tracks available rooms, while the other tracks ongoing meetings by their end times, ensuring we always assign the earliest available room.

⚙️

Algorithm

5 steps

1Step 1: Sort meetings by start times.
2Step 2: Use a min-heap to track the end times of meetings and the corresponding room numbers.
3Step 3: For each meeting, check if the earliest ending meeting has finished. If so, free up that room and assign it to the current meeting.
4Step 4: If no rooms are available, delay the meeting until a room becomes free, adjusting the meeting duration accordingly.
5Step 5: Track the number of meetings held in each room and return the room with the maximum meetings.

solution.py17 lines

1import heapq
2
3def meetingRooms(n, meetings):
4    meetings.sort(key=lambda x: x[0])
5    room_count = [0] * n
6    min_heap = []
7    for start, end in meetings:
8        while min_heap and min_heap[0][0] <= start:
9            _, room = heapq.heappop(min_heap)
10            heapq.heappush(min_heap, (end, room))
11            room_count[room] += 1
12            break
13        else:
14            earliest_end, room = heapq.heappop(min_heap)
15            heapq.heappush(min_heap, (earliest_end + (end - start), room))
16            room_count[room] += 1
17    return room_count.index(max(room_count))

ℹ

Complexity note: The sorting step takes O(n log n), and managing the heap operations takes O(log n) for each meeting, leading to an overall complexity of O(n log n).

1Prioritize room assignment based on earliest end times.
2Utilize heaps for efficient management of room availability.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.