**Merge overlapping intervals**

Given N events S = (e_{1},e_{2},…..e_{n}) with start time and end time ( (s_{1},e_{1}), (s_{2},e_{2}),(s_{3},e_{3}), …. (s_{n},e_{n})). Problem is to **merge overlapping intervals.** What are overlapping events or intervals? Events i and j overlap if start time of j^{th} event is less than end time of i^{th} event or vice-a-versa.

For example, [(1,3),(2,4),(5,8)] should be transformed into[(1,4),(5,8 )] as event 1 from (1,3 ) and event 2 from (2,4) are overlapping and will be merged into one as (1,4).

This problem is quite simple, however, we will understand concept of stacks and arrays by solving this.

**Merge overlapping intervals : Methods**

Let’s see brute force solution first. Take i^{th} event and compare start time of every j^{th} event with end time of i^{th}, if start time of j^{th} event is less than end time of ith event and end time of j^{th} event is greater than i^{th} event then update the end time of i^{th} event.

This solution has complexity of O(N^2). Can we do better than that?

How about sorting all events based on start time? If start time of i^{th} event is greater than (i-1)^{th} event’s end time, than start time of (i+1)^{th} event will be greater than (i-1)^{th} event. Hence, compare current event’s start time with previous event’s end time and update end time of previous event in case of overlap.

It’s required to keep track of last seen or updated event each time a new event is considered for overlap, stack is best data structure to be used when we are concerned about last thing first.

**Merge overlapping intervals: Algorithm**

1. Take event e from pool of events. 2. If stack is empty, push e to stack. 3. If stack is not empty, then pop event at top of stack call it e1. 3.1 Compare start time of e with end time of event e1. 3.2 If e.start < e1.end 3.2.1 if e.end > e1.end, update e1.end and push e1 on to stack. 3.2.1 if e.end < e1.end, push e1 onto stack. 3.3 Else push e to stack.

**Merge overlapping intervals implementation**

#include <stdio.h> #include<stdio.h> #include<stdlib.h> #include <string.h> #define STACK_SIZE 10 typedef struct Event{ int startTime; int endTime; int jobNum; }Event; typedef struct stack{ int top; Event items[STACK_SIZE]; }stack; void push(stack *ms, Event element){ if(ms->top < STACK_SIZE-1){ ms->items[++(ms->top)] = element; } else { printf("Stack is full\n"); } } Event pop (stack *ms){ if(ms->top >= 0){ return ms->items[(ms->top)--]; } else{ printf("Stack is empty\n"); } } int isEmpty(stack ms){ if(ms.top < 0) return 1; else return 0; } void swap(Event events[], int i, int j){ int tempStart = events[i].startTime; int tempEnd = events[i].endTime; int jobNum = events[i].jobNum; events[i].startTime = events[j].startTime ; events[i].endTime = events[j].endTime ; events[i].jobNum = events[j].jobNum; events[j].startTime = tempStart; events[j].endTime = tempEnd ; events[j].jobNum = jobNum; } int partition(Event events[], int start, int nEvents){ int i,j; i = start+1; j = nEvents; int pivot = events[start].startTime; while(i<=j){ while(i<=nEvents && events[i].startTime < pivot) i++; while(j>start && events[j].startTime >= pivot) j--; if(i<j){ swap(events, i, j); } } if(j>start) swap(events,start, j); return j; } void quicksort(Event events[], int start, int nEvents){ if(start < nEvents) { int pivot = partition(events, start, nEvents); quicksort(events, start, pivot-1); quicksort(events, pivot+1, nEvents); } } void mergeIntervals(Event events[], int nEvents){ int currentEventNum = 0; stack s; s.top = -1; quicksort(events, 0, nEvents-1); Event lastEvent; while(currentEventNum < nEvents){ Event currentEvent = events[currentEventNum]; if(!isEmpty(s)){ lastEvent = pop(&s); if(currentEvent.startTime < lastEvent.endTime){ if( currentEvent.endTime > lastEvent.endTime){ lastEvent.endTime = currentEvent.endTime; } push(&s,lastEvent); } else{ push(&s, lastEvent); push(&s, currentEvent); } } else{ push(&s, currentEvent); } currentEventNum++; } while(!isEmpty(s)){ lastEvent = pop(&s); printf("(%d,%d)", lastEvent.startTime,lastEvent.endTime); printf("\n"); } } int main(){ Event events[5]; events[0].startTime = 0; events[0].endTime = 2; events[0].jobNum = 1; events[1].startTime = 2; events[1].endTime = 3; events[1].jobNum = 2; events[2].startTime = 1; events[2].endTime = 5; events[2].jobNum = 3; events[3].startTime = 3; events[3].endTime = 7; events[3].jobNum = 4; events[4].startTime = 8; events[4].endTime = 9; events[4].jobNum = 5; mergeIntervals(events, 5); printf("\n"); return 0; }

Complexity of algorithm to **merge overlapping intervals** will be O(N log N) due to sorting with O(N) extra space.

Please share if something is wrong or missing. We would love to hear from hear. If you are interested in contributing to algorithm and me, please contact us.