1
/**
2
 * @param {number[][]} times
3
 * @param {number} targetFriend
4
 * @return {number}
5
 */
6
var smallestChair = function (times, targetFriend) {
7
  const [targetArrival] = times[targetFriend]; // we need only arrival time
8
  const arrivalQueue = times;
9
  const leavingQueue = [...times];
10
  arrivalQueue.sort((a, b) => a[0] - b[0]); // sort by arrival time
11
  leavingQueue.sort((a, b) => a[1] - b[1] || a[0] - b[0]); // sort by leaving time and if they are equal by arrival
12
  const chairsByLeaveTime = new Map(); // key - arrival time, value - chair index
13
  let chairsCount = 0;
14
  let arriving = 0,
15
    leaving = 0; // two pointers for keeping track of available chairs
16

17
  while (arriving < arrivalQueue.length) {
18
    let chairIdx;
19
    const arrival = arrivalQueue[arriving][0];
20
    const leave = leavingQueue[leaving][1];
21
    if (arrival < leave) {
22
      chairIdx = chairsCount++; // if no one is leaving, take a new chair
23
    } else {
24
      let freeChairIdx = leaving;
25
      chairIdx = chairsByLeaveTime.get(leavingQueue[freeChairIdx++][0]); // when arriaval time is less then or equal to the next leaving friend we can take her chair
26
      while (arrival >= leavingQueue[freeChairIdx][1]) {
27
        // to avoid situation when a few friends left already and the next chair in leaving queue is not the smallest
28
        const nextChair = chairsByLeaveTime.get(leavingQueue[freeChairIdx][0]);
29
        if (chairIdx > nextChair) {
30
          [leavingQueue[leaving], leavingQueue[freeChairIdx]] = [
31
            leavingQueue[freeChairIdx],
32
            leavingQueue[leaving],
33
          ]; // swap the front of the queue with the smallest chair owner
34
          chairIdx = nextChair;
35
        }
36
        ++freeChairIdx;
37
      }
38
      ++leaving;
39
    }
40
    if (targetArrival === arrival) {
41
      // we found the target, no need to continue
42
      return chairIdx;
43
    }
44
    chairsByLeaveTime.set(arrival, chairIdx); // as far as arrival time is distinct, we can use it as a key
45
    arriving++;
46
  }
47
};