The Number Of Smallest Unoccupied Chair

There is a party with n friends. The friends are numbered from 0 to n - 1. There are an unlimited number of chairs at the party. The chairs are numbered from 0 upwards

1942. The Number of the Smallest Unoccupied Chair

Difficulty: Medium

Link: LeetCode Problem

Problem Statement

There is a party with n friends. The friends are numbered from 0 to n - 1.

There are an unlimited number of chairs at the party. The chairs are numbered from 0 upwards.

When a friend arrives, they sit on the unoccupied chair with the smallest number.

• Example: If chairs 0, 1, and 5 are already taken, the next friend will sit on chair 2.

When a friend leaves, their chair becomes free right away. If another friend arrives at that exact same time, they can sit in that newly free chair.

You are given a 2D array called times. Each entry, times[i] = [arrivali, leavingi], tells us when friend i arrives and when they leave. All arrival times are different from each other.

You are also given a number called targetFriend.

Return the chair number that targetFriend sits on.

Examples

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. Chair 1 becomes empty.
• Friend 0 leaves at time 4. Chair 0 becomes empty.
• Friend 2 arrives at time 4 and sits on chair 0.

Friend 1 sat on chair 1. So the answer is 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. Chair 0 becomes empty.
• Friend 2 leaves at time 6. Chair 1 becomes empty.
• Friend 0 leaves at time 10. Chair 2 becomes empty.

Friend 0 sat on chair 2. So the answer is 2.

Constraints

• n == times.length
• 2 ≤ n ≤ 10⁴
• times[i].length == 2
• 1 ≤ arrivali < leavingi ≤ 10⁵
• 0 ≤ targetFriend ≤ n - 1
• Each arrival time is different.

Solution

The steps to solve this problem:

• First, we sort the friends by their arrival time.
• We use two min heaps:
  • One heap stores the available chair numbers.
  • The other heap stores the leaving times, along with which chair will become free at that time.
• At the start, there are no available chairs yet.
• For each friend, in order of arrival:
  • We first check the leaving-time heap. If someone's leaving time is less than or equal to the current friend's arrival time, that chair becomes free. We move it into the available-chairs heap. We repeat this for everyone who has already left by this time.
  • Next, we check if there are any available chairs:
    • If yes, we give the friend the smallest available chair.
    • If no, we give the friend a brand new chair number (the next number in line).
  • If this friend is our targetFriend, we return their chair number right away.
  • Otherwise, we add this friend's leaving time and chair number into the leaving-time heap, so we can free the chair later.

Code

class MinHeap {
  constructor(comparator) {
    this.heap = [];
    this.comparator = comparator;
  }

  size() { return this.heap.length; }
  isEmpty() { return this.heap.length === 0; }
  peek() { return this.heap[0]; }

  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._bubbleDown(0);
    }
    return top;
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.comparator(this.heap[parent], this.heap[i]) <= 0) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _bubbleDown(i) {
    const n = this.heap.length;
    while (true) {
      const left = 2 * i + 1, right = 2 * i + 2;
      let smallest = i;
      if (left < n && this.comparator(this.heap[left], this.heap[smallest]) < 0) smallest = left;
      if (right < n && this.comparator(this.heap[right], this.heap[smallest]) < 0) smallest = right;
      if (smallest === i) break;
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

var smallestChair = function(times, targetFriend) {
  const n = times.length;

  // Keep original friend index alongside their [arrival, leaving] time
  const friends = times.map((time, index) => ({ arrival: time[0], leaving: time[1], index }));
  friends.sort((a, b) => a.arrival - b.arrival);

  const availableChairs = new MinHeap((a, b) => a - b);          // just chair numbers
  const leavingEvents = new MinHeap((a, b) => a[0] - b[0]);      // [leaveTime, chairNumber]

  let nextNewChair = 0;

  for (const friend of friends) {
    // Free up any chairs whose occupant has already left by this arrival time
    while (!leavingEvents.isEmpty() && leavingEvents.peek()[0] <= friend.arrival) {
      const [, chairNumber] = leavingEvents.pop();
      availableChairs.push(chairNumber);
    }

    // Assign the smallest available chair, or mint a new one
    let assignedChair;
    if (!availableChairs.isEmpty()) {
      assignedChair = availableChairs.pop();
    } else {
      assignedChair = nextNewChair++;
    }

    if (friend.index === targetFriend) {
      return assignedChair;
    }

    leavingEvents.push([friend.leaving, assignedChair]);
  }

  return -1; // unreachable given valid input
};