Merge Intervals in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

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

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

int main(){
    Interval arr[]={{1,3},{2,4},{6,8},{7,9}};
    int n=4; qsort(arr,n,sizeof(Interval),cmp);
    int i=0;
    while(i<n){
        int start=arr[i].s, end=arr[i].e;
        while(i<n-1 && arr[i+1].s<=end){
            if(arr[i+1].e>end) end=arr[i+1].e;
            i++;
        }
        printf("[%d,%d] ",start,end);
        i++;
    }
}

C Output

Input:  
{[1,3], [2,4], [6,8], [7,9]}

Output:  
[1,4] [6,9]

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<pair<int,int>> v={{1,2},{3,5},{4,6},{7,8},{8,10}};
    sort(v.begin(),v.end());
    vector<pair<int,int>> res;
    for(auto &p:v){
        if(res.empty() || res.back().second < p.first) res.push_back(p);
        else res.back().second=max(res.back().second,p.second);
    }
    for(auto &p:res) cout<<"["<<p.first<<","<<p.second<<"] ";
}

C++ Output

Input:  
{[1,2], [3,5], [4,6], [7,8], [8,10]}  

Output:  
[1,2] [3,6] [7,10]

JAVA Program

import java.util.*;
class Main{
    public static void main(String[] args){
        int[][] arr={{5,6},{1,3},{2,4},{7,8}};
        Arrays.sort(arr,(a,b)->a[0]-b[0]);
        List<int[]> res=new ArrayList<>();
        for(int[] in:arr){
            if(res.isEmpty() || res.get(res.size()-1)[1]<in[0]) res.add(in);
            else res.get(res.size()-1)[1]=Math.max(res.get(res.size()-1)[1],in[1]);
        }
        for(int[] in:res) System.out.print("["+in[0]+","+in[1]+"] ");
    }
}

JAVA Output

Input:  
{[5,6], [1,3], [2,4], [7,8]

Output:  
[1,4] [5,6] [7,8]

Python Program

intervals=[[1,5],[2,3],[4,8],[10,12],[9,10]]
intervals.sort()
merged=[]
for s,e in intervals:
    if not merged or merged[-1][1] < s:
        merged.append([s,e])
    else:
        merged[-1][1]=max(merged[-1][1],e)
print(merged)

Python Output

Input:  
[[1,5], [2,3], [4,8], [10,12], [9,10] 

Output:  
[[1, 8], [9, 12]]

Deep Explanation

Example

Consider intervals as meeting times. If one meeting begins earlier than another ends, you can combine them into a single time block. For instance, if one meeting is 1–3 and another is 2–4, they are overlapping, so the combined block is 1–4.

Real-Life Analogy

Suppose highway repair teams are working on various sections of a highway. If their work zones overlap, you can consider it one bigger construction zone. This prevents unnecessary stops and restarts — just like merging intervals prevents storing duplicate blocks of time.

Why It Matters

Interval merging is a fundamental operation in calendar programs, CPU process scheduling, event timeline management, and scheduling systems. This is a favorite problem in coding interviews since it examines sorting ability, greedy merging knowledge, and delicate treatment of boundary cases.

Learning Insights

The secret to doing this efficiently is sorting on start times, then scanning and merging en route. Sorting guarantees that any overlapping intervals will be consecutive in the list so that they don't require nested loops. This solution takes O(n log n) time for sorting, with O(1) additional space if in-place merging is used.

Common Mistakes

Beginners often forget to sort first, which leads to incorrect merges. Another mistake is mishandling cases where intervals just touch at the boundary (e.g., [1,2] and [2,3]) — whether they merge depends on problem constraints, and interviewers sometimes test this edge case.

Real-World Use

Integrating intervals is ubiquitous: integrating intersecting meeting slots in a calendar, collapsing IP address ranges in networks, combining DNA sequence ranges in bioinformatics, and streamlining video editing timelines where there are overlapping clips.

SEO-Friendly Wrap-Up

Merging intervals is a fundamental algorithm for dealing with overlapping ranges efficiently in scheduling, resource allocation, and compression. With sorting and scanning the list, you can merge overlapping ranges in O(n log n) time, which is both efficient and space-friendly. Understanding this method aids in the solution of real-world problems such as calendar optimization, CPU scheduling, and event management, and is an interview coding must-know.