当前位置: 面试刷题>> 合并区间(经典算法150题)


题目描述

给定一个区间的集合,合并所有重叠的区间,并以 [start, end] 的形式返回合并后的结果。确保合并后的区间列表按非递减顺序排列,且合并后的每个区间的开始值小于或等于前一个区间的结束值。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间,因为它们是连续的。

PHP 示例代码

<?php

function merge($intervals) {
    if (empty($intervals)) {
        return [];
    }

    // 根据区间的起始位置进行排序
    usort($intervals, function($a, $b) {
        return $a[0] - $b[0];
    });

    $merged = [$intervals[0]]; // 初始化合并后的区间列表

    // 遍历排序后的区间,进行合并
    for ($i = 1; $i < count($intervals); $i++) {
        $current = $intervals[$i];
        $lastMerged = $merged[count($merged) - 1];

        // 如果当前区间的起始位置小于等于上一个合并区间的结束位置,则进行合并
        if ($current[0] <= $lastMerged[1]) {
            $lastMerged[1] = max($lastMerged[1], $current[1]); // 更新结束位置
        } else {
            // 如果不重叠,直接将当前区间加入合并列表
            $merged[] = $current;
        }
    }

    return $merged;
}

// 示例用法
$intervals = [[1,3],[2,6],[8,10],[15,18]];
print_r(merge($intervals));

?>

Python 示例代码

def merge(intervals):
    if not intervals:
        return []

    # 根据区间的起始位置进行排序
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    # 遍历排序后的区间,进行合并
    for interval in intervals[1:]:
        last_merged = merged[-1]

        # 如果当前区间的起始位置小于等于上一个合并区间的结束位置,则进行合并
        if interval[0] <= last_merged[1]:
            last_merged[1] = max(last_merged[1], interval[1])
        else:
            # 如果不重叠,直接将当前区间加入合并列表
            merged.append(interval)

    return merged

# 示例用法
intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge(intervals))

JavaScript 示例代码

function merge(intervals) {
    if (!intervals.length) {
        return [];
    }

    // 根据区间的起始位置进行排序
    intervals.sort((a, b) => a[0] - b[0]);

    let merged = [intervals[0]];

    // 遍历排序后的区间,进行合并
    for (let i = 1; i < intervals.length; i++) {
        let current = intervals[i];
        let lastMerged = merged[merged.length - 1];

        // 如果当前区间的起始位置小于等于上一个合并区间的结束位置,则进行合并
        if (current[0] <= lastMerged[1]) {
            lastMerged[1] = Math.max(lastMerged[1], current[1]); // 更新结束位置
        } else {
            // 如果不重叠,直接将当前区间加入合并列表
            merged.push(current);
        }
    }

    return merged;
}

// 示例用法
const intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log(merge(intervals));

以上代码均展示了如何合并给定区间列表的算法实现,并提供了示例用法。这些代码可以很好地满足面试要求,并可以在码小课网站上作为学习资源分享。

推荐面试题