Merge overlapping intervals (C)

Fork

#include <stdio.h>

int main() {
    printf("Hello world!\n");
    return 0;
}


#if 0 /* Sample code 8/
class Pair{
  public:
    int first, second;
    Pair(int x, int y){
      first = x;
      second = y; 
    }
};

vector<Pair> merge_intervals(vector<Pair>& v){
  vector<Pair> result;
  // write your code here
  return result; 
}
#endif

Fork

The goal of this exercise is to merge all the overlapping intervals of a given list to produce a list that has only mutually exclusive intervals.

Problem statement: You have an array (list) of interval pairs as input where each interval has a start and end timestamp, sorted by starting timestamps. Merge the overlapping intervals and return a new output array.

Consider an input array below. Intervals (1, 5), (3, 7), (4, 6), (6, 8) are overlapping so they should be merged to one interval (1, 8). Similarly, intervals (10, 12) and (12, 15) are also overlapping and should be merged to (10, 15).

This problem can be solved with a linear scan algorithm. The list of input intervals is given, and we’ll keep merged intervals in the output list. For each interval in the input list:

If the input interval is overlapping with the last interval in the output list, merge these two intervals and update the last interval of the output list with the merged interval.
Otherwise, add an input interval to the output list.
Runtime complexity: Linear, O(n)
O(n)

Memory complexity: Linear, O(n)
O(n)

Embed on website