aboutsummaryrefslogtreecommitdiff
path: root/smallest_range_convering_elem_k.c
diff options
context:
space:
mode:
Diffstat (limited to 'smallest_range_convering_elem_k.c')
-rw-r--r--smallest_range_convering_elem_k.c67
1 files changed, 67 insertions, 0 deletions
diff --git a/smallest_range_convering_elem_k.c b/smallest_range_convering_elem_k.c
new file mode 100644
index 0000000..3cb4a3d
--- /dev/null
+++ b/smallest_range_convering_elem_k.c
@@ -0,0 +1,67 @@
+// 632. Smallest Range Covering Elements from K Lists
+#include "leetcode.h"
+
+/*
+ * you have 'k' lists of sorted integers in non decreasing order. find the
+ * smallest range that includes at least one number from each of the 'k' lists.
+ * we define the range '[a, b]' is smaller than the range '[c, d]' if 'b - a < d
+ * - c' or 'a < c' if 'b - a == d - c'
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int *smallestRange(int **nums, int numsSize, int *numsColSize,
+ int *returnSize) {
+ int n = 0, idx = 0;
+ for (int i = 0; i < numsSize; i++)
+ n += numsColSize[i];
+ int *data = (int *)calloc(n, sizeof(int));
+ for (int i = 0; i < numsSize; i++)
+ for (int j = 0; j < numsColSize[i]; j++)
+ data[idx++] = nums[i][j] * 4096 | i;
+ qsort(data, n, sizeof(int), cmp);
+ int *ans = (int *)calloc(2, sizeof(int));
+ int left = 0, right = 0, list_cnt = 0,
+ min_range = (data[n - 1] >> 12) - (data[0] >> 1);
+ ans[0] = data[0] >> 12;
+ ans[1] = data[n - 1] >> 12;
+ idx = 0;
+ memset(numsColSize, 0, numsSize * sizeof(int));
+ while (right < n) {
+ int list_idx = data[right++] & 0xFFF;
+ numsColSize[list_idx]++;
+ if (numsColSize[list_idx] == 1) {
+ list_cnt++;
+ while (list_cnt == numsSize) {
+ int diff = (data[right - 1] >> 12) - (data[left] >> 12);
+ if (diff < min_range) {
+ ans[0] = data[left] >> 12;
+ ans[1] = data[right - 1] >> 12;
+ min_range = diff;
+ }
+ list_idx = data[left++] & 0xFFF;
+ numsColSize[list_idx]--;
+ if (!numsColSize[list_idx])
+ list_cnt--;
+ }
+ }
+ }
+ *returnSize = 2;
+ free(data);
+ return ans;
+}
+
+int main() {
+ int n1[3][5] = {{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}},
+ ncs1 = 3, rs1;
+ int n2[3][3] = {{1, 2, 3}, {1, 2, 3}, {1, 2, 3}}, ncs2 = 3, rs2;
+ int *sr1 = smallestRange((int **)n1, ARRAY_SIZE(n1), &ncs1, &rs1);
+ int *sr2 = smallestRange((int **)n2, ARRAY_SIZE(n2), &ncs2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", sr1[i]); // expect: 20 24
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", sr2[i]); // expect: 1 1
+ printf("\n");
+ free(sr1), free(sr2);
+}