leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

set_intersection_size_min_two.c (1794B)

 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
// 757. Set Intersection Size At Least Two
#include "leetcode.h"

/*
 * you are given a 2d integer array 'intervals' where 'intervals[i] = [start_i,
 * end_i]' represents all the integers from 'start_i' to 'end_i' inclusively. a
 * containing set is an array 'nums' where each interval from 'intervals' has at
 * least two integers in 'nums'. return the minimum possible size of a
 * containing set.
 */

int cmp(const void *a, const void *b) {
  int *aa = *(int **)a, *bb = *(int **)b;
  if (aa[1] == bb[1])
    return bb[0] - aa[0];
  return aa[1] - bb[1];
}

int intersectionSizeTwo(int **intervals, int intervalsSize,
                        int *intervalsColSize) {
  qsort(intervals, intervalsSize, sizeof(int *), cmp);
  int ans = 0, a = -1, b = -1;
  for (int i = 0; i < intervalsSize; i++) {
    int l = intervals[i][0], r = intervals[i][1];
    if (l > b) {
      a = r - 1;
      b = r;
      ans += 2;
    } else if (l > a) {
      a = b;
      b = r;
      ans++;
    }
  }
  return ans;
}

int main() {
  int i1i[3][2] = {{1, 3}, {3, 7}, {8, 9}};
  int i2i[4][2] = {{1, 3}, {1, 4}, {2, 5}, {3, 5}};
  int i3i[4][2] = {{1, 2}, {2, 3}, {2, 4}, {4, 5}};
  struct two_d_arr *i1 =
      two_d_arr_init(ARRAY_SIZE(i1i), ARRAY_SIZE(i1i[0]), i1i);
  struct two_d_arr *i2 =
      two_d_arr_init(ARRAY_SIZE(i2i), ARRAY_SIZE(i2i[0]), i2i);
  struct two_d_arr *i3 =
      two_d_arr_init(ARRAY_SIZE(i3i), ARRAY_SIZE(i3i[0]), i3i);
  printf("%d\n",
         intersectionSizeTwo(i1->arr, i1->row_size, i1->col_size)); // expect: 5
  printf("%d\n",
         intersectionSizeTwo(i2->arr, i2->row_size, i2->col_size)); // expect: 3
  printf("%d\n",
         intersectionSizeTwo(i3->arr, i3->row_size, i3->col_size)); // expect: 5
  two_d_arr_free(i1);
  two_d_arr_free(i2);
  two_d_arr_free(i3);
}