commit 132e2dca4c2cd33e3e8a4385c6e247ad1221947b
parent 6da48e38372d7c75cbf19c14abfe103fcb7783d1
Author: Jack Sangdahl <jack@pngu.org>
Date: Fri, 26 Dec 2025 20:47:59 -0700
2402. meeting rooms 3
Diffstat:
| M | meeting_rooms3.c | | | 128 | ++++++++++++++++++++++++++++++------------------------------------------------- |
| M | meeting_rooms3.py | | | 42 | +++++++++++++++++++++++++++--------------- |
2 files changed, 75 insertions(+), 95 deletions(-)
diff --git a/meeting_rooms3.c b/meeting_rooms3.c
@@ -17,93 +17,61 @@
* including 'b'.
*/
-void heapdown(int **room, int *heap, int heapsize) {
- int curr = 1;
- int child = curr << 1;
- while (child <= heapsize) {
- if (child + 1 <= heapsize &&
- room[heap[child + 1]][0] < room[heap[child]][0])
- child++;
- if (room[heap[child]][0] >= room[heap[curr]][0])
- break;
- heap[curr] ^= heap[child];
- heap[child] ^= heap[curr];
- heap[curr] ^= heap[child];
- curr = child;
- child <<= 1;
- }
-}
-void heapup(int **room, int *heap, int heapidx, int roomidx) {
- int curr = heapidx;
- int father = curr >> 1;
- while (father >= 1) {
- if (room[heap[father]][0] <= room[roomidx][0])
- break;
- heap[curr] = heap[father];
- curr = father;
- father >>= 1;
- }
- heap[curr] = roomidx;
-}
int cmp(const void *a, const void *b) {
- return (*(int **)a)[0] - (*(int **)b)[0];
+ int *aa = *(int **)a;
+ int *bb = *(int **)b;
+ return aa[0] - bb[0];
}
+
int mostBooked(int n, int **meetings, int meetingsSize, int *meetingsColSize) {
- long long **room = malloc(n * sizeof(long long *));
- for (int i = 0; i < n; i++) {
- room[i] = malloc(4 * sizeof(long long));
- room[i][0] = i;
- room[i][1] = i;
- room[i][2] = -1;
- room[i][3] = 0;
- }
- qsort(meetings, meetingsSize, sizeof(meetings[0]), cmp);
- int *nonbook = malloc((n + 1) * sizeof(int));
- int *booked = malloc((n + 1) * sizeof(int));
- int nonbookidx = 0; // 1~n
- int bookidx = 0; // 1~n
- for (int i = 0; i < n; i++) {
- heapup(room, nonbook, i + 1, nonbookidx++);
- }
- for (int i = 0; i < meetingsSize; i++) {
- long long poptime = meetings[i][0];
- int target = 0;
- if (nonbookidx == 0)
- poptime = fmax(poptime, room[booked[1]][0]);
- // booked ->nonbooked
- while (bookidx > 0 && room[booked[1]][0] <= poptime) {
- target = booked[1];
- room[target][0] = room[target][1];
- heapup(room, nonbook, ++nonbookidx, target);
- booked[1] = booked[bookidx--];
- heapdown(room, booked, bookidx);
+ qsort(meetings, meetingsSize, sizeof(int *), cmp);
+ int *cnt = (int *)calloc(n, sizeof(int)), i = 0;
+ long *timer = (long *)calloc(n, sizeof(long));
+ while (i < meetingsSize) {
+ int start = meetings[i][0], end = meetings[i][1];
+ int room = -1, earliest_room = -1;
+ long duration = end - start, earliest = LONG_MAX;
+ for (int j = 0; j < n; j++) {
+ if (timer[j] < earliest) {
+ earliest = timer[j];
+ earliest_room = j;
+ }
+ if (timer[j] <= start) {
+ room = i;
+ break;
+ }
}
- // nonbooked ->booked
- target = nonbook[1];
- room[target][2] = (room[target][2] <= meetings[i][0])
- ? meetings[i][1]
- : room[target][2] + meetings[i][1] - meetings[i][0];
- room[target][3] += 1;
- room[target][0] = room[target][2];
- heapup(room, booked, ++bookidx, target);
- nonbook[1] = nonbook[nonbookidx--];
- heapdown(room, nonbook, nonbookidx);
- }
- int ans = 0;
- int count = -1;
- for (int i = 0; i < n; i++) {
- if (room[i][3] > count) {
- count = room[i][3];
- ans = i;
+ if (room != -1) {
+ timer[room] = end;
+ cnt[room]++;
+ } else {
+ timer[earliest_room] += duration;
+ cnt[earliest_room]++;
}
+ i++;
}
-
- return ans;
+ int max = 0, idx = 0;
+ for (int j = 0; j < n; j++)
+ if (cnt[j] > max) {
+ max = cnt[j];
+ idx = j;
+ }
+ free(cnt);
+ free(timer);
+ return idx;
}
int main() {
- int m1[5][2] = {{0, 10}, {1, 5}, {2, 7}, {3, 4}},
- m2[5][2] = {{1, 20}, {2, 10}, {3, 5}, {4, 9}, {6, 8}}, *mcs1, *mcs2;
- printf("%d\n", mostBooked(2, (int **)m1, 5, mcs1)); // expect: 0
- printf("%d\n", mostBooked(3, (int **)m2, 5, mcs2)); // expect: 1
+ int m1i[5][2] = {{0, 10}, {1, 5}, {2, 7}, {3, 4}};
+ int m2i[5][2] = {{1, 20}, {2, 10}, {3, 5}, {4, 9}, {6, 8}};
+ struct two_d_arr *m1 =
+ two_d_arr_init(ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i);
+ struct two_d_arr *m2 =
+ two_d_arr_init(ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i);
+ printf("%d\n",
+ mostBooked(2, m1->arr, m1->row_size, m1->col_size)); // expect: 0
+ printf("%d\n",
+ mostBooked(3, m2->arr, m2->row_size, m2->col_size)); // expect: 1
+ two_d_arr_free(m1);
+ two_d_arr_free(m2);
}
diff --git a/meeting_rooms3.py b/meeting_rooms3.py
@@ -24,22 +24,34 @@ class Solution(object):
:type meetings: List[List[int]]
:rtype: int
"""
- ready = [r for r in range(n)]
- rooms = []
- heapify(ready)
- ans = [0] * n
- for s, e in sorted(meetings):
- while rooms and rooms[0][0] <= s:
- t, r = heappop(rooms)
- heappush(ready, r)
- if ready:
- r = heappop(ready)
- heappush(rooms, [e, r])
+ meetings.sort()
+ cnt = [0] * n
+ timer = [0] * n
+ i = 0
+ while i < len(meetings):
+ start, end = meetings[i]
+ duration, earliest = end - start, float("inf")
+ room, earliest_room = -1, -1
+ for j in range(n):
+ if timer[j] < earliest:
+ earliest = timer[j]
+ earliest_room = j
+ if timer[j] <= start:
+ room = j
+ break
+ if room != -1:
+ timer[room] = end
+ cnt[room] += 1
else:
- t, r = heappop(rooms)
- heappush(rooms, [t + e - s, r])
- ans[r] += 1
- return ans.index(max(ans))
+ timer[earliest_room] += duration
+ cnt[earliest_room] += 1
+ i += 1
+ mx, idx = 0, 0
+ for j in range(n):
+ if cnt[j] > mx:
+ mx = cnt[j]
+ idx = j
+ return idx
if __name__ == "__main__":
