1942. The Number of the Smallest Unoccupied Chair
The Number of the Smallest Unoccupied Chair (LeetCode 1942) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.
How to solve The Number of the Smallest Unoccupied Chair
The Number of the Smallest Unoccupied Chair is a Scheduling and Minimum Cost problem, part of Heap (Priority Queue) Patterns. Solve scheduling and optimization problems using priority queue with greedy approach.
Work towards the solution in these steps:
- Sort times by arrival time.
- for each arrival_i find the smallest unoccupied chair and mark it as occupied until leaving_i.
The reference solution runs in O(n log n) time and O(n) space.
The The Number of the Smallest Unoccupied Chair solution and editorial walks through the full approach with reference code.
Problem statement
There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.
- For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.
When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.
You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.
Return the chair number that the friend numbered targetFriend will sit on.
Example 1:
Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1 Output: 1 Explanation: - Friend 0 arrives at time 1 and sits on chair 0. - Friend 1 arrives at time 2 and sits on chair 1. - Friend 1 leaves at time 3 and chair 1 becomes empty. - Friend 0 leaves at time 4 and chair 0 becomes empty. - Friend 2 arrives at time 4 and sits on chair 0. Since friend 1 sat on chair 1, we return 1.
Example 2:
Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0 Output: 2 Explanation: - Friend 1 arrives at time 1 and sits on chair 0. - Friend 2 arrives at time 2 and sits on chair 1. - Friend 0 arrives at time 3 and sits on chair 2. - Friend 1 leaves at time 5 and chair 0 becomes empty. - Friend 2 leaves at time 6 and chair 1 becomes empty. - Friend 0 leaves at time 10 and chair 2 becomes empty. Since friend 0 sat on chair 2, we return 2.
Constraints:
- n == times.length
- 2 <= n <= 104
- times[i].length == 2
- 1 <= arrivali < leavingi <= 105
- 0 <= targetFriend <= n - 1
- Each arrivali time is distinct.
Topics and companies
Topics: Array, Hash Table, Heap (Priority Queue).
How to practise The Number of the Smallest Unoccupied Chair on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n) time and O(n) space.
Open The Number of the Smallest Unoccupied Chair in the code editor, or read the The Number of the Smallest Unoccupied Chair editorial for a worked solution with its approach and complexity analysis.
Where The Number of the Smallest Unoccupied Chair sits in the DSA pattern sheet
- Heap (Priority Queue) Patterns pattern guide
- Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
- The full DSA patterns sheet
Problems related to The Number of the Smallest Unoccupied Chair
Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:
- Furthest Building You Can Reach — Medium, same subpattern
- IPO — Hard, same subpattern
- Longest Happy String — Medium, same subpattern
- Maximum Average Pass Ratio — Medium, same subpattern
- Meeting Rooms II — Medium, same subpattern
- Meeting Rooms III — Hard, same subpattern
The Number of the Smallest Unoccupied Chair FAQ
What is the LeetCode number of The Number of the Smallest Unoccupied Chair?
The Number of the Smallest Unoccupied Chair is LeetCode problem 1942, rated Medium.
What pattern is used to solve The Number of the Smallest Unoccupied Chair?
The Number of the Smallest Unoccupied Chair is a Scheduling and Minimum Cost problem. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.
What is the time complexity of The Number of the Smallest Unoccupied Chair?
The reference solution runs in O(n log n) time and O(n) space.