LeetCode //C - 56. Merge Intervals-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 56. Merge Intervals。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

56. Merge Intervals

Given an array of intervals where intervals[i] = $start_i, end_i]$ , merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

$1 <= intervals.length <= 10^4$
intervals[i].length == 2
$0 <= start_i <= end_i <= 10^4$

From: LeetCode
Link: 56. Merge Intervals

Solution:

Ideas：

To merge overlapping intervals:

First, we sort the intervals based on the starting times.
Then, we start with the first interval and compare its end with the start of the next interval.
If they overlap (i.e., the end of the current interval is greater than or equal to the start of the next interval), we merge them.
If they don’t overlap, we simply move to the next interval.
Continue this process until all intervals are processed.

This code first sorts the intervals by their start times. Then, it goes through each interval, checking if it can be merged with the previous one. If it can, it updates the end time of the merged interval. If not, it adds a new interval to the merged list.

The function returns the merged intervals and updates the returnSize and returnColumnSizes accordingly.文章来源地址https://www.toymoban.com/news/detail-652578.html

Code:

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int compare(const void* a, const void* b) {
    return (*(int**)a)[0] - (*(int**)b)[0];
}

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

    // Sort the intervals based on start times
    qsort(intervals, intervalsSize, sizeof(int*), compare);

    // Create an array to store merged intervals
    int** merged = (int**)malloc(intervalsSize * sizeof(int*));
    int mergedSize = 0;

    for (int i = 0; i < intervalsSize; i++) {
        // If merged array is empty or current interval does not overlap with previous, just add to merged array
        if (mergedSize == 0 || merged[mergedSize - 1][1] < intervals[i][0]) {
            merged[mergedSize] = (int*)malloc(2 * sizeof(int));
            merged[mergedSize][0] = intervals[i][0];
            merged[mergedSize][1] = intervals[i][1];
            mergedSize++;
        } else {
            // Merge the overlapping intervals
            if (merged[mergedSize - 1][1] < intervals[i][1]) {
                merged[mergedSize - 1][1] = intervals[i][1];
            }
        }
    }

    // Set the returnSize and returnColumnSizes
    *returnSize = mergedSize;
    *returnColumnSizes = (int*)malloc(mergedSize * sizeof(int));
    for (int i = 0; i < mergedSize; i++) {
        (*returnColumnSizes)[i] = 2; // Since each interval consists of 2 integers
    }

    return merged;
}