๐ฅ LeetCode Solution | NAITIK-builds
2402. Meeting Rooms III
๐ด Hard โข ๐ข Premium โข โ Solved โข ๐ 45.7% Accepted
๐ Problem Description
You are given an integer
n
. There aren
rooms numbered from0
ton - 1
.You are given a 2D integer array
meetings
wheremeetings[i] = [starti, endi]
means that a meeting will be held during the half-closed time interval[starti, endi)
. All the values ofstarti
are unique.
๐ฏ Meeting Allocation Rules:
- ๐ Each meeting will take place in the unused room with the lowest number
- โฐ If there are no available rooms, the meeting will be delayed until a room becomes free
- ๐ 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
๐งช Test Cases
Example 1:
Example 2:
๐ฏ 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:
- ๐ป GitHub: NAITIK-builds
- ๐ผ LinkedIn: naitik-vishwakarma
- ๐ง Email: [email protected]