Merging Overlapping Intervals

Given an array intervals where each element is a pair [start, end], merge all overlapping entervals and return a list of non-overlapping intervals that cover all input intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap → merged into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Adjacent intervals with shared endpoint are considered overlapping.

Implementation in C

int compare_intervals(const void* a, const void* b) {
    int* ia = *(int**)a;
    int* ib = *(int**)b;
    return (ia[0] < ib[0]) ? -1 : (ia[0] > ib[0]);
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize,
            int* returnSize, int** returnColumnSizes) {
    if (intervalsSize == 0) {
        *returnSize = 0;
        return NULL;
    }

    // Sort by start point
    qsort(intervals, intervalsSize, sizeof(int*), compare_intervals);

    // Allocate result buffer
    int** result = malloc(intervalsSize * sizeof(int*));
    *returnColumnSizes = malloc(intervalsSize * sizeof(int));
    for (int i = 0; i < intervalsSize; ++i) {
        result[i] = malloc(2 * sizeof(int));
        (*returnColumnSizes)[i] = 2;
    }

    int merged_count = 0;
    result[merged_count][0] = intervals[0][0];
    result[merged_count][1] = intervals[0][1];

    for (int i = 1; i < intervalsSize; ++i) {
        int current_start = intervals[i][0];
        int current_end = intervals[i][1];
        int last_end = result[merged_count][1];

        if (current_start > last_end) {
            // No overlap: append new interval
            ++merged_count;
            result[merged_count][0] = current_start;
            result[merged_count][1] = current_end;
        } else {
            // Overlap: extend the end of the last interval
            result[merged_count][1] = (current_end > last_end) ? current_end : last_end;
        }
    }

    *returnSize = merged_count + 1;
    return result;
}

The algorithm sorts intervals by their starting points, then scans left to right, greedily merging consecutive intervals whenever the current start lies within or immediately after the previous interval’s end.

Searching a Sorted 2D Matrix

You're given an m x n matrix where each row is sorted in ascending order left-to-right, and each column is sorted top-to-bottom. Efficiently determine weather target exists in the matrix.

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: same matrix, target = 20
Output: false

Implementation in C

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    if (matrixSize == 0 || *matrixColSize == 0) return false;

    int row = matrixSize - 1;
    int col = 0;

    while (row >= 0 && col < *matrixColSize) {
        int val = matrix[row][col];
        if (val == target) {
            return true;
        } else if (val > target) {
            --row; // Too large → move up
        } else {
            ++col; // Too small → move right
        }
    }

    return false;
}

This solution starts from the bottom-left corner. At each step, it eliminates either a full row (if current value exceeds target) or a full column (if current value is smaller), achieving O(m + n) time complexity without extra space.