Question

How to merge overlapping ranges (start,end),(start,end) in C

Answer 1

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

typedef struct {
    int start;
    int end;
} Range;

int cmp_ranges(const void *a, const void *b) {
    const Range *ra = (const Range *)a;
    const Range *rb = (const Range *)b;
    
    return ra->start - rb->start;
}

Range* merge_ranges(Range *ranges, int n, int *out_size) {
    if (n == 0) {
        *out_size = 0;
        return NULL;
    }

    // Sort ranges by start
    qsort(ranges, n, sizeof(Range), cmp_ranges);

    // Allocate output array
    Range *merged = malloc(n * sizeof(Range));
    int m = 0;

    merged[m++] = ranges[0];

    for (int i = 1; i < n; i++) {
        Range *last = &merged[m - 1];

        if (ranges[i].start > last->end) {
            // No overlap → append
            merged[m++] = ranges[i];
        } else {
            // Overlap → merge
            if (ranges[i].end > last->end)
                last->end = ranges[i].end;
        }
    }

    *out_size = m;
    
    return merged;
}

int main() {
    // initializing an array of structures
    Range ranges[] = {
        {302, 447}, {488, 489}, {121, 234}, {200, 421}, {140, 354}
    };
    int n = sizeof(ranges) / sizeof(ranges[0]);

    int out_size;
    Range *merged = merge_ranges(ranges, n, &out_size);

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

    free(merged);
    
    return 0;
}


/*
run:

(121, 447) (488, 489) 

*/

 

70+ SQL courses for beginners and professionals