aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--num_smallest_unoccupied_char.c96
-rw-r--r--num_smallest_unoccupied_char.py40
2 files changed, 136 insertions, 0 deletions
diff --git a/num_smallest_unoccupied_char.c b/num_smallest_unoccupied_char.c
new file mode 100644
index 0000000..b8babad
--- /dev/null
+++ b/num_smallest_unoccupied_char.c
@@ -0,0 +1,96 @@
+// 1942. The Number of the Smallest Unoccupied Chair
+#include "leetcode.h"
+
+/*
+ * there is a party where 'n' friends numbered from 0 to 'n - 1' are attending.
+ * there is an infinite number of chairs in this part that are numbered from 0
+ * to 'infinity'. when a friend arrives at the party, they sit on the unoccupied
+ * chair with the smallest number. 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] = [arrival[i], leaving[i]]' indicating
+ * the arrival and leaving times of the i'th friend respectively. and an integer
+ * 'targetFriend'. all arrival times are distinct. return the chair number that
+ * the friend numbered 'targetFriend' will sit on.
+ */
+
+int cmp(const void *a, const void *b) {
+ return (*(int **)a)[0] - (*(int **)b)[0];
+}
+
+void heap_down(int **chair, int *heap, int heap_size) {
+ int curr = 1, child = curr * 2;
+ while (child <= heap_size) {
+ if (child + 1 <= heap_size &&
+ chair[heap[child + 1]][0] < chair[heap[child]][0])
+ child++;
+ if (chair[heap[curr]][0] < chair[heap[child]][0])
+ break;
+ int tmp = heap[child];
+ heap[child] = heap[curr];
+ heap[curr] = tmp;
+ curr = child;
+ child *= 2;
+ }
+}
+
+void heap_up(int **chair, int *heap, int idx, int val) {
+ int curr = idx, parent = curr / 2;
+ while (parent >= 1) {
+ if (chair[heap[parent]][0] <= chair[val][0])
+ break;
+ heap[curr] = heap[parent];
+ curr = parent;
+ parent /= 2;
+ }
+ heap[curr] = val;
+}
+
+int smallestChair(int **times, int timesSize, int *timesColSize,
+ int targetFriend) {
+ int ans = 0, valid_idx = timesSize, invalid_idx = 0;
+ int **chair = (int **)malloc(timesSize * sizeof(int *));
+ int **qdata = (int **)malloc(timesSize * sizeof(int *));
+ int *valid = (int *)malloc((timesSize + 1) * sizeof(int));
+ int *invalid = (int *)malloc((timesSize + 1) * sizeof(int));
+ for (int i = 0; i < timesSize; i++) {
+ qdata[i] = (int *)malloc(3 * sizeof(int));
+ qdata[i][0] = times[i][0];
+ qdata[i][1] = times[i][1];
+ qdata[i][2] = i;
+ chair[i] = (int *)malloc(3 * sizeof(int));
+ chair[i][0] = chair[i][1] = i;
+ chair[i][2] = 0;
+ valid[i + 1] = i;
+ }
+ qsort(qdata, timesSize, sizeof(qdata[0]), cmp);
+ for (int i = 0; i < timesSize; i++) {
+ while (invalid_idx && chair[invalid[1]][0] <= qdata[i][0]) {
+ int target = invalid[i];
+ chair[target][0] = chair[target][1];
+ heap_up(chair, valid, ++valid_idx, target);
+ invalid[1] = invalid[invalid_idx--];
+ heap_down(chair, invalid, invalid_idx);
+ }
+ if (targetFriend == qdata[i][2])
+ ans = chair[valid[1]][1];
+ int target = valid[1];
+ chair[target][0] = chair[target][2] = qdata[i][1];
+ heap_up(chair, invalid, ++invalid_idx, target);
+ valid[1] = valid[valid_idx--];
+ heap_down(chair, valid, valid_idx);
+ }
+ for (int i = 0; i < timesSize; i++)
+ free(chair[i]), free(qdata[i]);
+ free(chair), free(qdata), free(valid), free(invalid);
+ return ans;
+}
+
+int main() {
+ int t1[3][2] = {{1, 4}, {2, 3}, {4, 6}}, t2[3][2] = {{3, 10}, {1, 5}, {2, 6}},
+ tcs1 = 2, tcs2 = 2;
+ printf("%d\n",
+ smallestChair((int **)t1, ARRAY_SIZE(t1), &tcs1, 1)); // expect: 1
+ printf("%d\n",
+ smallestChair((int **)t2, ARRAY_SIZE(t2), &tcs2, 0)); // expect: 2
+}
diff --git a/num_smallest_unoccupied_char.py b/num_smallest_unoccupied_char.py
new file mode 100644
index 0000000..f8d1073
--- /dev/null
+++ b/num_smallest_unoccupied_char.py
@@ -0,0 +1,40 @@
+# 1942. The Number of the Smallest Unoccupied Chair
+import heapq
+
+"""
+there is a party where 'n' friends numbered from 0 to 'n - 1' are attending.
+there is an infinite number of chairs in this part that are numbered from 0
+to 'infinity'. when a friend arrives at the party, they sit on the unoccupied
+chair with the smallest number. 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] = [arrival[i], leaving[i]]' indicating
+the arrival and leaving times of the i'th friend respectively. and an integer
+'targetFriend'. all arrival times are distinct. return the chair number that
+the friend numbered 'targetFriend' will sit on.
+"""
+
+
+class Solution(object):
+ def smallestChair(self, times, targetFriend):
+ """
+ :type times: List[List[int]]
+ :type targetFriend: int
+ :rtype: int
+ """
+ order = sorted(range(len(times)), key=lambda x: times[x][0])
+ empty, taken = list(range(len(times))), []
+ for i in order:
+ arrive, leave = times[i]
+ while taken and taken[0][0] <= arrive:
+ heapq.heappush(empty, heapq.heappop(taken)[1])
+ seat = heapq.heappop(empty)
+ if i == targetFriend:
+ return seat
+ heapq.heappush(taken, (leave, seat))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.smallestChair(times=[[1, 4], [2, 3], [4, 6]], targetFriend=1))
+ print(obj.smallestChair(times=[[3, 10], [1, 5], [2, 6]], targetFriend=0))