1942. The Number of the Smallest Unoccupied Chair LeetCode Solution

Last updated: February 25, 2025

In this guide, you will get 1942. The Number of the Smallest Unoccupied Chair LeetCode Solution with the best time and space complexity. The solution to The Number of the Smallest Unoccupied Chair problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
The Number of the Smallest Unoccupied Chair solution in C++
The Number of the Smallest Unoccupied Chair solution in Java
The Number of the Smallest Unoccupied Chair solution in Python
Additional Resources

1942. The Number of the Smallest Unoccupied Chair LeetCode Solution image

Problem Statement of The Number of the Smallest Unoccupied Chair

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.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1942. The Number of the Smallest Unoccupied Chair LeetCode Solution in C++

class Solution {
 public:
  int smallestChair(vector<vector<int>>& times, int targetFriend) {
    int nextUnsatChair = 0;
    priority_queue<int, vector<int>, greater<>> emptyChairs;
    using P = pair<int, int>;  // (leaving, chair)
    priority_queue<P, vector<P>, greater<>> occupied;

    for (int i = 0; i < times.size(); ++i)
      times[i].push_back(i);

    ranges::sort(times);

    for (const vector<int>& time : times) {
      const int arrival = time[0];
      const int leaving = time[1];
      const int i = time[2];
      while (!occupied.empty() && occupied.top().first <= arrival)
        emptyChairs.push(occupied.top().second), occupied.pop();
      if (i == targetFriend)
        return emptyChairs.empty() ? nextUnsatChair : emptyChairs.top();
      if (emptyChairs.empty())
        occupied.emplace(leaving, nextUnsatChair++);
      else
        occupied.emplace(leaving, emptyChairs.top()), emptyChairs.pop();
    }

    throw;
  }
};
/* code provided by PROGIEZ */

1942. The Number of the Smallest Unoccupied Chair LeetCode Solution in Java

class Solution {
  public int smallestChair(int[][] times, int targetFriend) {
    int nextUnsatChair = 0;
    PriorityQueue<Integer> emptyChairs = new PriorityQueue<>();
    PriorityQueue<Pair<Integer, Integer>> occupied =
        new PriorityQueue<>(Comparator.comparing(Pair::getKey));

    for (int i = 0; i < times.length; ++i) {
      int[] time = times[i];
      time = Arrays.copyOf(time, time.length + 1);
      time[time.length - 1] = i;
      times[i] = time;
    }

    Arrays.sort(times, (a, b) -> Integer.compare(a[0], b[0]));

    for (int[] time : times) {
      final int arrival = time[0];
      final int leaving = time[1];
      final int i = time[2];
      while (!occupied.isEmpty() && occupied.peek().getKey() <= arrival)
        emptyChairs.add(occupied.poll().getValue());
      if (i == targetFriend)
        return emptyChairs.isEmpty() ? nextUnsatChair : emptyChairs.peek();
      if (emptyChairs.isEmpty())
        occupied.add(new Pair<>(leaving, nextUnsatChair++));
      else
        occupied.add(new Pair<>(leaving, emptyChairs.poll()));
    }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

1942. The Number of the Smallest Unoccupied Chair LeetCode Solution in Python

class Solution:
  def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
    nextUnsatChair = 0
    emptyChairs = []
    occupied = []  # (leaving, chair)

    for i in range(len(times)):
      times[i].append(i)

    times.sort(key=lambda x: x[0])

    for arrival, leaving, i in times:
      while len(occupied) > 0 and occupied[0][0] <= arrival:
        unsatChair = heapq.heappop(occupied)[1]
        heapq.heappush(emptyChairs, unsatChair)
      if i == targetFriend:
        return emptyChairs[0] if len(emptyChairs) > 0 else nextUnsatChair
      if len(emptyChairs) == 0:
        heapq.heappush(occupied, (leaving, nextUnsatChair))
        nextUnsatChair += 1
      else:
        emptyChair = heapq.heappop(emptyChairs)
        heapq.heappush(occupied, (leaving, emptyChair))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents