aboutsummaryrefslogtreecommitdiff
path: root/insert_interval.c
blob: 21025daa8a5e136f48ed6da73e104d9bae6594b1 (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
// 57. Insert Interval
#include "leetcode.h"

/*
 * return array of arrays of size '*returnSize'
 * the sizes of the arrays are returned as '*returnColumnSizes' array
 * note both returned array and '*columnSizes' array must be malloced (assume
 * caller free()'s memory)
 */

int **insert(int **intervals, int intervalsSize, int *intervalsColSize,
             int *newInterval, int newIntervalSize, int *returnSize,
             int **returnColumnSizes) {
  *returnSize = 0;
  int left = newInterval[0], right = newInterval[1];
  bool placed = false;
  int **ans = malloc(sizeof(int *) * (intervalsSize + 1));
  *returnColumnSizes = malloc(sizeof(int *) * (intervalsSize + 1));
  for (int i = 0; i < intervalsSize; i++) {
    int *intval = intervals[i];
    if (intval[0] > right) {
      if (!placed) {
        int *tmp = malloc(sizeof(int) * 2);
        tmp[0] = left;
        tmp[1] = right;
        (*returnColumnSizes)[*returnSize] = 2;
        ans[(*returnSize)++] = tmp;
        placed = true;
      }
      int *tmp = malloc(sizeof(int) * 2);
      memcpy(tmp, intval, sizeof(int) * 2);
      (*returnColumnSizes)[*returnSize] = 2;
      ans[(*returnSize)++] = tmp;
    } else if (intval[1] < left) {
      int *tmp = malloc(sizeof(int) * 2);
      memcpy(tmp, intval, sizeof(int) * 2);
      (*returnColumnSizes)[*returnSize] = 2;
      ans[(*returnSize)++] = tmp;
    } else {
      left = fmin(left, intval[0]);
      right = fmax(right, intval[1]);
    }
  }
  if (!placed) {
    int *tmp = malloc(sizeof(int) * 2);
    tmp[0] = left;
    tmp[1] = right;
    (*returnColumnSizes)[*returnSize] = 2;
    ans[(*returnSize)++] = tmp;
  }
  return ans;
}