Merge overlapping intervals

Merge overlapping intervals

Given N events S = (e1,e2,…..en) with start time and end time ( (s1,e1), (s2,e2),(s3,e3), …. (sn,en)). Problem is to merge overlapping intervals. What are overlapping events or intervals? Events i and j overlap if start time of jth event is less than end time of ith 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 ith event and compare start time of every jth event with end time of ith, if start time of jth event is less than end time of ith event and end time of jth event is greater than ith event then update the end time of ith 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 ith 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.

  • Andrea

    I think step 5 in the algorithm should read “If start time of e is less than end time of e1, and end time of e is greater than end time of e1, update end time of e1”

    • http://algorithmsandme.in/ Jitendra Sangar

      Thanks for pointing out. Will correct it.

  • Исай

    thank you

  • Исай

    I think there is error at the code at partition function. The function sort jobs by end time but it should sort jobs by start time. At lines 57, 61, 63 instead of end_time should be start_time.

    • http://algorithmsandme.in/ Jitendra Sangar

      Thanks for pointing out. Corrected it