aboutsummaryrefslogtreecommitdiff
path: root/divide_interval_min_group.c
blob: 32481f3e4de9fc7f5f87fad5065be88d15f73d2f (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
// 2406. Divide Intervals Into Minimum Number of Groups
#include "leetcode.h"

/*
 * you are given a 2d integer array 'intervals' where 'intervals[i] = [left,
 * right]' represents the inclusive interval '[left, right]'. you have to divide
 * the intervals into one or more groups such that each interval is in exactly
 * one group, and no two intervals that are in the same group intersect each
 * other. return the minimum number of groups you need to make. two intervals
 * intersect if there is at least one common number between them.
 */

int minGroups(int **intervals, int intervalsSize, int *intervalsColSize) {
  int max_val = 0;
  for (int i = 0; i < intervalsSize; i++)
    if (intervals[i][1] > max_val)
      max_val = intervals[i][1];
  int *arr = (int *)calloc(max_val + 2, sizeof(int));
  for (int i = 0; i < intervalsSize; i++) {
    arr[intervals[i][0]]++;
    arr[intervals[i][1] + 1]--;
  }
  int ans = 0, curr = 0;
  for (int i = 0; i <= max_val; i++) {
    curr += arr[i];
    if (curr > ans)
      ans = curr;
  }
  free(arr);
  return ans;
}

int main() {
  int i1[5][2] = {{5, 10}, {6, 8}, {1, 5}, {2, 3}, {1, 10}}, ics1 = 5;
  int i2[4][2] = {{1, 3}, {5, 6}, {8, 10}, {11, 13}}, ics2 = 4;
  printf("%d\n", minGroups((int **)i1, ARRAY_SIZE(i1), &ics1)); // expect: 3
  printf("%d\n", minGroups((int **)i2, ARRAY_SIZE(i2), &ics2)); // expect: 1
}