merge_intervals.c

/*
 * Leecode 56. Merge Intervals
 * 
 * Example 1:
 * Input: [[1,3],[2,6],[8,10],[15,18]]
 * Output: [[1,6],[8,10],[15,18]]
 * Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
 
 * Example 2:
 * Input: [[1,4],[4,5]]
 * Output: [[1,5]]
 * Explanation: Intervals [1,4] and [4,5] are considered overlapping.
 *
 * NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
 */

#include <stdio.h>
#include <stdlib.h>

struct Interval {
  int start;
  int end;
};

int cmp(const void *a, const void *b)
{
  return ((struct Interval*)a)->start - ((struct Interval*)b)->start;
}

struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) 
{
  qsort(intervals, intervalsSize, sizeof(struct Interval), cmp);

  *returnSize = intervalsSize;
  struct Interval* res = (struct Interval*)malloc(sizeof(struct Interval) * intervalsSize);

  if(intervalsSize == 0 || intervalsSize == 1)
    return intervals;

  int i, j, t_s, t_e;
  j = 0;
  t_s = intervals[0].start;
  t_e = intervals[0].end;

  for(int i = 1; i < intervalsSize; ++i) {
    if(t_e >= intervals[i].end) {
      --(*returnSize);
    } else if (t_e >= intervals[i].start) {
      t_e = intervals[i].end;
      --(*returnSize);
    } else {
      res[j].start = t_s;
      res[j].end = t_e;
      ++j;
      t_s = intervals[i].start;
      t_e = intervals[i].end;
    }
  }
  res[j].start = t_s;
  res[j].end = t_e;

  return res;
}

int main(char argc, char **argv)
{
  int input_size = 4;

  struct Interval* input = (struct Interval*)malloc(sizeof(struct Interval) * input_size);

  // [1, 4] [2, 5] [3, 4] [7, 100]
  input[0].start = 1;
  input[0].end = 4;

  input[1].start = 2;
  input[1].end = 5;

  input[2].start = 3;
  input[2].end = 4;

  input[3].start = 7;
  input[3].end = 100;

  int output_size = 0;
  struct Interval* output = merge(input, input_size, &output_size);

  for(int i=0; i<input_size; i++) {
    printf("[%d, %d] ", input[i].start, input[i].end);
  }
  printf("\n");
  for(int i=0; i<output_size; i++) {
    printf("[%d, %d] ", output[i].start, output[i].end);
  }

  return 0;
}