1942. The Number of the Smallest Unoccupied Chair

Problem

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.

Solution

/**
 * @param {number[][]} times
 * @param {number} targetFriend
 * @return {number}
 */
var smallestChair = function(times, targetFriend) {
    var emptyChairs = new Set();
    var max = -1;
    var list = times.reduce((arr, item, i) => {
        arr.push({ i, type: 1, time: item[0] });
        arr.push({ i, type: 2, time: item[1] });
        return arr;
    }, []).sort((a, b) => {
        // be careful if someone's arrival time equals the other's leave time
        // make sure we process leave one first
        if (a.time === b.time) {
            return b.type - a.type;
        }
        return a.time - b.time;
    });
    var map = {};
    for (var i = 0; i < list.length; i++) {
        var item = list[i];
        if (item.type === 1) {
            // someone arrival
            if (emptyChairs.size) {
                // found empty chair someone left before
                map[item.i] = findMin(emptyChairs);
                emptyChairs.delete(map[item.i]);
            } else {
                // go to the last chair
                map[item.i] = max + 1;
                max = map[item.i];
            }
            if (item.i === targetFriend) {
                break;
            }
        } else {
            // someone leave
            emptyChairs.add(map[item.i]);
        }
    }
    return map[targetFriend];
};

// should replace set with min heap
// so that time complexity could be O(nlog(n))
var findMin = function(list) {
    return Array.from(list).sort((a, b) => a - b)[0];
};

Explain:

nope.

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(n).