feat: solve No.1942

BaffinLee · BaffinLee · commit 681f0383fe6c · 2023-05-10T01:07:19.000+08:00
diff --git a/1901-2000/1942. The Number of the Smallest Unoccupied Chair.md b/1901-2000/1942. The Number of the Smallest Unoccupied Chair.md
@@ -71,7 +71,56 @@ Since friend 0 sat on chair 2, we return 2.
 ## Solution
 
 ```javascript
-
+/**
+ * @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:**
@@ -80,5 +129,5 @@ nope.
 
 **Complexity:**
 
-* Time complexity : O(n).
+* Time complexity : O(n^2).
 * Space complexity : O(n).
