diff options
author | Jack Sangdahl <[email protected]> | 2025-09-20 22:27:01 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-20 22:27:01 -0600 |
commit | 927ff9c0b810a6dbcf12f2389423e2cf0200c7c1 (patch) | |
tree | 65223f526f2293172060c6964a07a7ebcc9a1a46 | |
parent | d5e6bc72a4a72b64bb237fe8a1c22cae73f0dcab (diff) | |
download | leetcode-927ff9c0b810a6dbcf12f2389423e2cf0200c7c1.tar.gz leetcode-927ff9c0b810a6dbcf12f2389423e2cf0200c7c1.zip |
1912. design movie rental system
-rw-r--r-- | design_movie_rental.c | 424 | ||||
-rw-r--r-- | design_movie_rental.py | 63 |
2 files changed, 487 insertions, 0 deletions
diff --git a/design_movie_rental.c b/design_movie_rental.c new file mode 100644 index 0000000..d53d496 --- /dev/null +++ b/design_movie_rental.c @@ -0,0 +1,424 @@ +// 1912. Design Movie Rental System +#include "leetcode.h" + +#define MAX_SIZE 100005 + +typedef struct AvNode { + int price; + int shop; + unsigned pr; + struct AvNode *l, *r; +} AvNode; + +typedef struct RNode { + int price; + int shop; + int movie; + unsigned pr; + struct RNode *l, *r; +} RNode; + +static inline int cmp_av(int p1, int s1, int p2, int s2) { + if (p1 != p2) + return (p1 < p2) ? -1 : 1; + if (s1 != s2) + return (s1 < s2) ? -1 : 1; + return 0; +} + +static inline int cmp_r(int p1, int s1, int m1, int p2, int s2, int m2) { + if (p1 != p2) + return (p1 < p2) ? -1 : 1; + if (s1 != s2) + return (s1 < s2) ? -1 : 1; + if (m1 != m2) + return (m1 < m2) ? -1 : 1; + return 0; +} + +static AvNode *av_merge(AvNode *a, AvNode *b) { + if (!a) + return b; + if (!b) + return a; + if (a->pr < b->pr) { + a->r = av_merge(a->r, b); + return a; + } else { + b->l = av_merge(a, b->l); + return b; + } +} + +static void av_split(AvNode *root, int price, int shop, AvNode **left, + AvNode **right) { + if (!root) { + *left = *right = NULL; + return; + } + if (cmp_av(root->price, root->shop, price, shop) < 0) { + av_split(root->r, price, shop, &root->r, right); + *left = root; + } else { + av_split(root->l, price, shop, left, &root->l); + *right = root; + } +} + +static AvNode *av_insert(AvNode *root, AvNode *node) { + if (!root) + return node; + if (node->pr < root->pr) { + AvNode *l, *r; + av_split(root, node->price, node->shop, &l, &r); + node->l = l; + node->r = r; + return node; + } else { + if (cmp_av(node->price, node->shop, root->price, root->shop) < 0) + root->l = av_insert(root->l, node); + else + root->r = av_insert(root->r, node); + return root; + } +} + +static AvNode *av_erase(AvNode *root, int price, int shop) { + if (!root) + return NULL; + int c = cmp_av(price, shop, root->price, root->shop); + if (c == 0) { + AvNode *t = av_merge(root->l, root->r); + free(root); + return t; + } else if (c < 0) { + root->l = av_erase(root->l, price, shop); + } else { + root->r = av_erase(root->r, price, shop); + } + return root; +} + +static void av_collect_k(AvNode *root, int *out, int *cnt, int k) { + if (!root || *cnt >= k) + return; + av_collect_k(root->l, out, cnt, k); + if (*cnt < k) { + out[(*cnt)++] = root->shop; + } + if (*cnt < k) + av_collect_k(root->r, out, cnt, k); +} + +static void av_free(AvNode *root) { + if (!root) + return; + av_free(root->l); + av_free(root->r); + free(root); +} + +static RNode *r_merge(RNode *a, RNode *b) { + if (!a) + return b; + if (!b) + return a; + if (a->pr < b->pr) { + a->r = r_merge(a->r, b); + return a; + } else { + b->l = r_merge(a, b->l); + return b; + } +} + +static void r_split(RNode *root, int price, int shop, int movie, RNode **left, + RNode **right) { + if (!root) { + *left = *right = NULL; + return; + } + if (cmp_r(root->price, root->shop, root->movie, price, shop, movie) < 0) { + r_split(root->r, price, shop, movie, &root->r, right); + *left = root; + } else { + r_split(root->l, price, shop, movie, left, &root->l); + *right = root; + } +} + +static RNode *r_insert(RNode *root, RNode *node) { + if (!root) + return node; + if (node->pr < root->pr) { + RNode *l, *r; + r_split(root, node->price, node->shop, node->movie, &l, &r); + node->l = l; + node->r = r; + return node; + } else { + if (cmp_r(node->price, node->shop, node->movie, root->price, root->shop, + root->movie) < 0) + root->l = r_insert(root->l, node); + else + root->r = r_insert(root->r, node); + return root; + } +} + +static RNode *r_erase(RNode *root, int price, int shop, int movie) { + if (!root) + return NULL; + int c = cmp_r(price, shop, movie, root->price, root->shop, root->movie); + if (c == 0) { + RNode *t = r_merge(root->l, root->r); + free(root); + return t; + } else if (c < 0) { + root->l = r_erase(root->l, price, shop, movie); + } else { + root->r = r_erase(root->r, price, shop, movie); + } + return root; +} + +static void r_collect_k(RNode *root, int (*out)[2], int *cnt, int k) { + if (!root || *cnt >= k) + return; + r_collect_k(root->l, out, cnt, k); + if (*cnt < k) { + out[*cnt][0] = root->shop; + out[*cnt][1] = root->movie; + (*cnt)++; + } + if (*cnt < k) + r_collect_k(root->r, out, cnt, k); +} + +static void r_free(RNode *root) { + if (!root) + return; + r_free(root->l); + r_free(root->r); + free(root); +} + +typedef struct { + uint64_t *keys; + int *vals; + unsigned char *used; + size_t cap; + size_t mask; +} HashMap; + +static size_t nextPow2(size_t x) { + size_t p = 1; + while (p < x) + p <<= 1; + return p; +} + +static HashMap *hashmapCreate(size_t expected) { + size_t cap = nextPow2(expected * 2 + 8); + HashMap *m = (HashMap *)malloc(sizeof(HashMap)); + m->cap = cap; + m->mask = cap - 1; + m->keys = (uint64_t *)malloc(sizeof(uint64_t) * cap); + m->vals = (int *)malloc(sizeof(int) * cap); + m->used = (unsigned char *)malloc(sizeof(unsigned char) * cap); + memset(m->used, 0, cap); + return m; +} + +static void hashmapPut(HashMap *m, uint64_t key, int val) { + uint64_t h = key * 11400714819323198485ull; + size_t idx = (size_t)h & m->mask; + while (m->used[idx]) { + if (m->keys[idx] == key) { + m->vals[idx] = val; + return; + } + idx = (idx + 1) & m->mask; + } + m->used[idx] = 1; + m->keys[idx] = key; + m->vals[idx] = val; +} + +static int hashmapGet(HashMap *m, uint64_t key) { + uint64_t h = key * 11400714819323198485ull; + size_t idx = (size_t)h & m->mask; + size_t start = idx; + while (m->used[idx]) { + if (m->keys[idx] == key) + return m->vals[idx]; + idx = (idx + 1) & m->mask; + if (idx == start) + break; + } + return -1; +} + +typedef struct { + int n; + int m; + HashMap *priceMap; + AvNode **available; + RNode *rentedRoot; +} MovieRentingSystem; + +static AvNode *new_avnode(int price, int shop) { + AvNode *p = (AvNode *)malloc(sizeof(AvNode)); + p->price = price; + p->shop = shop; + p->pr = ((unsigned)rand() << 16) ^ (unsigned)rand(); + p->l = p->r = NULL; + return p; +} + +static RNode *new_rnode(int price, int shop, int movie) { + RNode *p = (RNode *)malloc(sizeof(RNode)); + p->price = price; + p->shop = shop; + p->movie = movie; + p->pr = ((unsigned)rand() << 16) ^ (unsigned)rand(); + p->l = p->r = NULL; + return p; +} + +MovieRentingSystem *movieRentingSystemCreate(int n, int **entries, + int entriesSize, + int *entriesColSize) { + srand(1234567); + MovieRentingSystem *obj = + (MovieRentingSystem *)malloc(sizeof(MovieRentingSystem)); + obj->n = n; + obj->m = entriesSize; + obj->priceMap = hashmapCreate((size_t)entriesSize + 4); + obj->available = (AvNode **)calloc(MAX_SIZE, sizeof(AvNode *)); + obj->rentedRoot = NULL; + for (int i = 0; i < entriesSize; ++i) { + int shop = entries[i][0]; + int movie = entries[i][1]; + int price = entries[i][2]; + uint64_t key = (((uint64_t)movie) << 32) | (uint32_t)shop; + hashmapPut(obj->priceMap, key, price); + AvNode *node = new_avnode(price, shop); + obj->available[movie] = av_insert(obj->available[movie], node); + } + return obj; +} + +int *movieRentingSystemSearch(MovieRentingSystem *obj, int movie, + int *retSize) { + int *res = (int *)malloc(sizeof(int) * 5); + *retSize = 0; + if (!obj) + return res; + if (movie < 0 || movie >= MAX_SIZE) + return res; + AvNode *root = obj->available[movie]; + if (!root) + return res; + av_collect_k(root, res, retSize, 5); + return res; +} + +void movieRentingSystemRent(MovieRentingSystem *obj, int shop, int movie) { + if (!obj) + return; + uint64_t key = (((uint64_t)movie) << 32) | (uint32_t)shop; + int price = hashmapGet(obj->priceMap, key); + if (price < 0) + return; + obj->available[movie] = av_erase(obj->available[movie], price, shop); + RNode *rn = new_rnode(price, shop, movie); + obj->rentedRoot = r_insert(obj->rentedRoot, rn); +} + +void movieRentingSystemDrop(MovieRentingSystem *obj, int shop, int movie) { + if (!obj) + return; + uint64_t key = (((uint64_t)movie) << 32) | (uint32_t)shop; + int price = hashmapGet(obj->priceMap, key); + if (price < 0) + return; + obj->rentedRoot = r_erase(obj->rentedRoot, price, shop, movie); + AvNode *an = new_avnode(price, shop); + obj->available[movie] = av_insert(obj->available[movie], an); +} + +int **movieRentingSystemReport(MovieRentingSystem *obj, int *retSize, + int **retColSize) { + int **res = (int **)malloc(sizeof(int *) * 5); + *retColSize = (int *)malloc(sizeof(int) * 5); + *retSize = 0; + if (!obj) + return res; + int buf[5][2]; + int cnt = 0; + r_collect_k(obj->rentedRoot, buf, &cnt, 5); + for (int i = 0; i < cnt; ++i) { + res[i] = (int *)malloc(sizeof(int) * 2); + res[i][0] = buf[i][0]; + res[i][1] = buf[i][1]; + (*retColSize)[i] = 2; + (*retSize)++; + } + return res; +} + +void movieRentingSystemFree(MovieRentingSystem *obj) { + if (!obj) + return; + if (obj->available) { + for (int i = 0; i < MAX_SIZE; ++i) + if (obj->available[i]) + av_free(obj->available[i]); + free(obj->available); + } + if (obj->rentedRoot) + r_free(obj->rentedRoot); + if (obj->priceMap) { + free(obj->priceMap->keys); + free(obj->priceMap->vals); + free(obj->priceMap->used); + free(obj->priceMap); + } + free(obj); +} + +int main() { + int entries_input[6][3] = {{0, 1, 5}, {0, 2, 6}, {0, 3, 7}, + {1, 1, 4}, {1, 2, 7}, {2, 1, 5}}; + int retSize, *retColSize; + struct two_d_arr *entries = two_d_arr_init( + ARRAY_SIZE(entries_input), ARRAY_SIZE(entries_input[0]), entries_input); + MovieRentingSystem *obj = movieRentingSystemCreate( + 3, entries->arr, entries->row_size, entries->col_size); + int *s1 = movieRentingSystemSearch(obj, 1, &retSize); + for (int i = 0; i < retSize; i++) + printf("%d ", s1[i]); + printf("\n"); + free(s1); + movieRentingSystemRent(obj, 0, 1); + movieRentingSystemRent(obj, 1, 2); + int **r1 = movieRentingSystemReport(obj, &retSize, &retColSize); + for (int i = 0; i < retSize; i++) { + for (int j = 0; j < retColSize[i]; j++) + printf("%d ", r1[i][j]); + printf("\n"); + } + printf("\n"); + for (int i = 0; i < retSize; i++) + free(r1[i]); + free(r1); + movieRentingSystemDrop(obj, 1, 2); + int *s2 = movieRentingSystemSearch(obj, 2, &retSize); + for (int i = 0; i < retSize; i++) + printf("%d ", s2[i]); + printf("\n"); + free(s2); + two_d_arr_free(entries); + movieRentingSystemFree(obj); +} diff --git a/design_movie_rental.py b/design_movie_rental.py new file mode 100644 index 0000000..384ed12 --- /dev/null +++ b/design_movie_rental.py @@ -0,0 +1,63 @@ +# 1912. Design Movie Rental System +from collections import defaultdict + +from sortedcontainers import SortedList + + +class MovieRentingSystem(object): + def __init__(self, n, entries): + """ + :type n: int + :type entries: List[List[int]] + """ + self.shops = defaultdict(SortedList) + self.shop_movie = {} + self.rented = SortedList() + for s, m, p in entries: + self.shops[m].add((p, s)) + self.shop_movie[s, m] = p + + def search(self, movie): + """ + :type movie: int + :rtype: List[int] + """ + return [i for _, i in self.shops[movie][:5]] + + def rent(self, shop, movie): + """ + :type shop: int + :type movie: int + :rtype: None + """ + price = self.shop_movie[shop, movie] + self.shops[movie].remove((price, shop)) + self.rented.add((price, shop, movie)) + + def drop(self, shop, movie): + """ + :type shop: int + :type movie: int + :rtype: None + """ + price = self.shop_movie[shop, movie] + self.shops[movie].add((price, shop)) + self.rented.remove((price, shop, movie)) + + def report(self): + """ + :rtype: List[List[int]] + """ + return [[i, j] for _, i, j in self.rented[:5]] + + +if __name__ == "__main__": + obj = MovieRentingSystem( + 3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]] + ) + print(obj.search(1)) + obj.rent(0, 1) + obj.rent(1, 2) + print(obj.report()) + obj.drop(1, 2) + print(obj.search(2)) |