🚀

End of Year Sale: Use Coupon Code END2025 to Get Extra 25% Off.

11DAYS
:
19HOURS
:
53MINUTES
:
46SECONDS

Leetcode Problem 1942. The Number of the Smallest Unoccupied Chair

1942. The Number of the Smallest Unoccupied Chair

Leetcode Solutions

Priority Queue and Min Heap Approach

  1. Sort the times array based on arrival times.
  2. Initialize two priority queues (min heaps): free_chairs for available chairs and occupied_chairs for chairs that are currently occupied.
  3. Fill free_chairs with all possible chair numbers (from 0 to n-1).
  4. Iterate through the sorted times array. a. For each friend, release any chairs from occupied_chairs whose departure time is less than or equal to the current arrival time. b. Assign the smallest available chair from free_chairs to the current friend. c. If the current friend is the targetFriend, return the assigned chair number. d. Add the current friend's departure time and assigned chair number to occupied_chairs.
  5. Return the chair number assigned to targetFriend.
UML Thumbnail

Simulation with Seat Availability Tracking

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...