๐Ÿ”ฅ LeetCode Solution | NAITIK-builds

2402. Meeting Rooms III

๐Ÿ”ด Hard โ€ข ๐Ÿข Premium โ€ข โœ… Solved โ€ข ๐Ÿ“Š 45.7% Accepted


๐Ÿ“‹ Problem Description

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

๐ŸŽฏ Meeting Allocation Rules:

  1. ๐Ÿ  Each meeting will take place in the unused room with the lowest number
  2. โฐ If there are no available rooms, the meeting will be delayed until a room becomes free
  3. ๐Ÿ“… When a room becomes unused, meetings that have an earlier original start time should be given the room

๐ŸŽฏ Return: The number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.


๐Ÿ’ก Algorithm & Approach

๐Ÿ” Strategy: Priority Queue + Greedy Allocation

Key Insights:

  • ๐Ÿ“Š Use two priority queues to efficiently manage room states
  • ๐Ÿ”„ Sort meetings by start time for proper processing order
  • ๐ŸŽฏ Greedy assignment to lowest-numbered available room
  • โฐ Handle delays by extending meeting duration when all rooms busy

๐Ÿ“ˆ Complexity Analysis:

  • Time Complexity: O(m log m + m log n) where m = meetings, n = rooms
  • Space Complexity: O(n) for tracking room states

๐Ÿ–ฅ๏ธ C++ Implementation

โŽ—
โœ“
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        // ๐Ÿ“Š Sort meetings by start time
        sort(meetings.begin(), meetings.end());

        // ๐Ÿ“‹ Track meeting count per room
        vector<int> room_meeting_count(n, 0);

        // ๐ŸŸข Min-heap for free rooms (lowest room number first)
        priority_queue<int, vector<int>, greater<int>> free_rooms;
        for (int i = 0; i < n; ++i) {
            free_rooms.push(i);
        }

        // ๐Ÿ”ด Min-heap for busy rooms (earliest end time first)
        using pii = pair<long long, int>;
        priority_queue<pii, vector<pii>, greater<pii>> busy_rooms;

        for (const auto& meeting : meetings) {
            int start = meeting[0], end = meeting[1];
            long long duration = end - start;

            // ๐Ÿ”„ Free up rooms that have finished
            while (!busy_rooms.empty() && busy_rooms.top().first <= start) {
                free_rooms.push(busy_rooms.top().second);
                busy_rooms.pop();
            }

            if (!free_rooms.empty()) {
                // โœ… Assign to available room
                int room = free_rooms.top();
                free_rooms.pop();
                busy_rooms.emplace(end, room);
                room_meeting_count[room]++;
            } else {
                // โฐ All rooms busy - delay meeting
                auto [available_time, room] = busy_rooms.top();
                busy_rooms.pop();
                busy_rooms.emplace(available_time + duration, room);
                room_meeting_count[room]++;
            }
        }

        // ๐Ÿ† Find room with most meetings (lowest number if tie)
        int max_meetings = 0, result_room = 0;
        for (int i = 0; i < n; ++i) {
            if (room_meeting_count[i] > max_meetings) {
                max_meetings = room_meeting_count[i];
                result_room = i;
            }
        }

        return result_room;
    }
};

๐Ÿงช Test Cases

Example 1:

โŽ—
โœ“
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0

Explanation: 
- At time 0: Meeting starts in room 0
- At time 1: Meeting starts in room 1
- At time 2: Both rooms busy, meeting delayed
- At time 3: Both rooms busy, meeting delayed
- At time 5: Room 1 free, delayed meeting starts in room 1
- At time 10: Room 0 free, last meeting starts in room 0
Both rooms held 2 meetings, return lowest number (0)

Example 2:

โŽ—
โœ“
1
2
3
4
5
6
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1

Explanation: 
Room 0 held 1 meeting, rooms 1 and 2 each held 2 meetings
Return room 1 (lowest number among rooms with max meetings)

๐ŸŽฏ Key Learning Points

๐Ÿ—๏ธ Data Structure Insights:

  • Two Priority Queues: Efficiently separate free and busy room management
  • Min-Heap Strategy: Always get the lowest-numbered available room
  • Time-based Processing: Handle room availability with timestamp tracking

โšก Algorithm Techniques:

  • Greedy Approach: Always choose optimal room assignment
  • Event Processing: Sort meetings by start time for proper handling
  • Delay Management: Extend meeting duration when all rooms are occupied

๐Ÿ”ข Edge Case Handling:

  • Tie-breaking: Return lowest room number when multiple rooms have same count
  • Overflow Prevention: Use long long for time calculations

Solution Summary ๐Ÿš€ Solved by NAITIK-builds LeetCode DSA Journey โ€ข Daily Problem Solving Future SDE ๐Ÿ’ป ๐Ÿ“Š Acceptance Rate: 45.7% โ€ข 165,183 Accepted


๐ŸŒŸ Connect with me:

Edit
Pub: 11 Jul 2025 09:37 UTC
Views: 6