Skip to content

1942. The Number of the Smallest Unoccupied Chair 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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) -> 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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 time: time[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))