diff options
-rw-r--r-- | rearranging_fruits.c | 104 | ||||
-rw-r--r-- | rearranging_fruits.py | 39 |
2 files changed, 143 insertions, 0 deletions
diff --git a/rearranging_fruits.c b/rearranging_fruits.c new file mode 100644 index 0000000..4252d05 --- /dev/null +++ b/rearranging_fruits.c @@ -0,0 +1,104 @@ +// 2561. Rearranging Fruits +#include "leetcode.h" + +/* + * you have two fruit baskests containing 'n' fruits each. you are given two + * indexed integer arrays 'basket1' and 'basket2' representing the cost of fruit + * in each baset. you want o make both baskets equal. to do so, you can use the + * following operation as many times as you want: chose two indices 'i' and 'j' + * and swap the i'th fruit of 'basket1' with the j'th fruit of 'basket2'. the + * cost of the swap is 'min(basket1[i], basket2[j])'. two baskets are considered + * equal if sorting them according to the fruit cost makes them exactly the same + * baksets. return the minimum cost to make both baskets equal or -1 if + * impossible. + */ + +struct map_entry { + int key; + int val; +}; + +struct map { + struct map_entry *entries; + int size; + int capacity; +}; + +void map_init(struct map *obj) { + obj->capacity = 16; + obj->size = 0; + obj->entries = + (struct map_entry *)malloc(obj->capacity * sizeof(struct map_entry)); +} + +void map_insert(struct map *obj, int key, int delta) { + for (int i = 0; i < obj->size; i++) + if (obj->entries[i].key == key) { + obj->entries[i].val += delta; + return; + } + if (obj->size == obj->capacity) { + obj->capacity *= 2; + obj->entries = (struct map_entry *)realloc( + obj->entries, obj->capacity * sizeof(struct map_entry)); + } + obj->entries[obj->size].key = key; + obj->entries[obj->size].val = delta; + obj->size++; +} + +int cmp(const void *a, const void *b) { + struct map_entry *aa = (struct map_entry *)a; + struct map_entry *bb = (struct map_entry *)b; + return aa->key - bb->key; +} + +void map_sort(struct map *obj) { + qsort(obj->entries, obj->size, sizeof(struct map_entry), cmp); +} + +long long minCost(int *basket1, int basket1Size, int *basket2, + int basket2Size) { + long long ans = 0; + struct map map; + map_init(&map); + for (int i = 0; i < basket1Size; i++) { + map_insert(&map, basket1[i], 1); + map_insert(&map, basket2[i], -1); + } + map_sort(&map); + if (!map.size) + return 0; + int m = map.entries[0].key; + int *arr = NULL, arr_size = 0, arr_capacity = 0; + for (int i = 0; i < map.size; i++) { + int val = map.entries[i].key, key = map.entries[i].val; + if (key % 2) { + free(map.entries); + if (arr) + free(arr); + return -1; + } + int cnt = abs(key) / 2; + for (int j = 0; j < cnt; j++) { + if (arr_size == arr_capacity) { + arr_capacity = !arr_capacity ? 1 : arr_capacity * 2; + arr = (int *)realloc(arr, arr_capacity * sizeof(int)); + } + arr[arr_size++] = val; + } + } + for (int i = 0; i < arr_size / 2; i++) + ans += (arr[i] < 2 * m) ? arr[i] : 2 * m; + free(map.entries), free(arr); + return ans; +} + +int main() { + int b11[] = {4, 2, 2, 2}, b21[] = {1, 4, 1, 2}; + int b12[] = {2, 3, 4, 1}, b22[] = {3, 2, 5, 1}; + printf("%lld\n", + minCost(b11, ARRAY_SIZE(b11), b21, ARRAY_SIZE(b21))); // expect: 1 + printf("%lld\n", + minCost(b12, ARRAY_SIZE(b12), b22, ARRAY_SIZE(b22))); // expect: -1 +} diff --git a/rearranging_fruits.py b/rearranging_fruits.py new file mode 100644 index 0000000..7040731 --- /dev/null +++ b/rearranging_fruits.py @@ -0,0 +1,39 @@ +# 2561. Rearranging Fruits +from collections import Counter + +""" +you have two fruit baskests containing 'n' fruits each. you are given two +indexed integer arrays 'basket1' and 'basket2' representing the cost of fruit +in each baset. you want o make both baskets equal. to do so, you can use the +following operation as many times as you want: chose two indices 'i' and 'j' +and swap the i'th fruit of 'basket1' with the j'th fruit of 'basket2'. the +cost of the swap is 'min(basket1[i], basket2[j])'. two baskets are considered +equal if sorting them according to the fruit cost makes them exactly the same +baksets. return the minimum cost to make both baskets equal or -1 if +impossible. +""" + + +class Solution(object): + def minCost(self, basket1, basket2): + """ + :type basket1: List[int] + :type basket2: List[int] + :rtype: int + """ + cnt = Counter(basket1 + basket2) + for i in cnt: + if cnt[i] % 2: + return -1 + cnt[i] >>= 1 + a1 = list((Counter(basket1) - cnt).elements()) + a2 = list((Counter(basket2) - cnt).elements()) + low = min(cnt) + c = sorted(a1 + a2) + return sum(min(low * 2, c[i]) for i in range(len(a1))) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minCost(basket1=[4, 2, 2, 2], basket2=[1, 4, 1, 2])) + print(obj.minCost(basket1=[2, 3, 4, 1], basket2=[3, 2, 5, 1])) |