aboutsummaryrefslogtreecommitdiff
path: root/smallest_range_convering_elem_k.c
blob: 3cb4a3d2e47077808783930bf9133da988660755 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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);
}