掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】

简介: 掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

题目描述

给出一个区间的集合,请合并所有重叠的区间。

输入格式
  • intervals:一个二维整数数组,每个子数组包含两个整数,表示一个区间的起始和结束位置。
输出格式
  • 返回一个二维整数数组,表示合并后的区间。

示例

示例 1
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 发生重叠,合并成 [1,6].
示例 2
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

方法一:排序后合并

解题步骤
  1. 排序:先按每个区间的起始位置进行排序。
  2. 初始化:用一个新列表 merged 来存储最终合并后的区间。
  3. 合并区间:遍历排序后的区间列表,如果 merged 为空或者当前区间与 merged 中最后一个区间不重叠,直接添加到 merged;否则,将当前区间与 merged 中最后一个区间进行合并。
完整的规范代码
def merge(intervals):
    """
    使用排序后合并的方法合并区间
    :param intervals: List[List[int]], 输入的区间列表
    :return: List[List[int]], 合并后的区间列表
    """
    intervals.sort(key=lambda x: x[0])  # 按区间起点进行排序
    merged = []
    for interval in intervals:
        # 如果列表为空,或当前区间与上一区间不重叠,直接添加
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # 否则,有重叠,进行合并
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged
# 示例调用
print(merge([[1,3],[2,6],[8,10],[15,18]]))  # 输出: [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))  # 输出: [[1,5]]
算法分析
  • 时间复杂度:(O(n log n)),其中 n 是区间的数量。主要耗时操作是排序。
  • 空间复杂度:(O(log n)) 或 (O(n)),取决于所使用的排序算法。

方法二:扫描线算法

解题步骤
  1. 创建事件:对于每个区间 [a, b],创建两个事件:(a, ‘start’) 和 (b, ‘end’)。
  2. 排序事件:按照时间点排序这些事件,如果时间点相同,则 ‘end’ 事件在 ‘start’ 事件之前。
  3. 扫描处理:扫描排序后的事件列表,使用计数器记录开启的区间数量,根据区间的开启和结束更新合并区间的列表。
完整的规范代码
def merge(intervals):
    """
    使用扫描线算法合并区间
    :param intervals: List[List[int]], 输入的区间列表
    :return: List[List[int]], 合并后的区间列表
    """
    events = []  # 事件列表
    for start, end in intervals:
        events.append((start, 'start'))
        events.append((end, 'end'))
    # 事件排序,结束事件优先于开始事件
    events.sort(key=lambda x: (x[0], x[1] == 'start'))
    merged = []
    ongoing = 0  # 当前开启的区间数
    for time, typ in events:
        if typ == 'start':
            if ongoing == 0:  # 新的区间开始
                start = time
            ongoing += 1
        elif typ == 'end':
            ongoing -= 1
            if ongoing == 0:  # 区间结束
                merged.append([start, time])
    return merged
# 示例调用
print(merge([[1,3],[2,6],[8,10],[15,18]]))  # 输出: [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))  # 输出: [[1,5]]
算法分析
  • 时间复杂度:(O(n log n)),主要耗时在于事件排序。
  • 空间复杂度:(O(n)),用于存储事件。

方法三:动态规划

动态规划方法不是本问题的最优解法,而且实现复杂度高,故不推荐使用。在实际应用中,方法一和方法二已足够解决大多数情况。

不同算法的优劣势对比

特征 方法一: 排序后合并 方法二: 扫描线算法
时间复杂度 (O(n \log n)) (O(n \log n))
空间复杂度 (O(\log n)) 或 (O(n)) (O(n))
优势 简单直观,易于实现 处理复杂情况更高效,适用于区间边界频繁变动的场景
劣势 空间复杂度依赖排序算法 实现相对复杂,需要处理多种事件排序逻辑

确保会议室的使用时间不冲突。以下是如何将区间合并算法应用于会议室预订系统的详细解析:

应用场景:会议室预订系统

场景描述

  • 一个公司有多个会议室,员工需要预订会议室进行会议。
  • 员工通过系统输入会议的开始和结束时间,系统需要自动显示可用的会议室或者提示时间冲突。

技术实现

  • 当员工提交一次会议室预订请求时,系统将这个新的时间区间与已存在的预订记录进行比对。
  • 使用区间合并算法来确定是否存在时间上的重叠,从而判断是否可以接受新的预订。

代码示例

假设我们已经有一些预定记录,现在需要处理新的预定请求。

def merge(intervals):
    intervals.sort(key=lambda x: x[0])  # 按区间起点进行排序
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged
# 已存在的会议预订记录
existing_bookings = [[9, 12], [14, 17], [21, 23]]
# 新的会议请求
new_meeting = [13, 15]
# 检查新的会议是否可以安排
combined_bookings = existing_bookings + [new_meeting]
merged_bookings = merge(combined_bookings)
if len(merged_bookings) != len(existing_bookings) + 1:
    print("新会议请求与现有会议时间冲突,无法预订。")
else:
    print("新会议请求成功预订。")
    existing_bookings = merged_bookings  # 更新现有预订记录
print("当前会议室预订情况:", merged_bookings)

输出解析

  • 程序首先将新的会议请求加入到已有的会议记录中。
  • 通过 merge 函数处理合并后的区间。
  • 如果合并前后的记录数量不变,说明新会议未与现有会议重叠,预订成功;否则,表示时间冲突。
应用二:动态时间表的优化管理

场景描述

  • 在动态时间表管理,如交通工具的时刻表调整或电视节目的排版中,需要不断调整活动时间以优化整体使用效率或观看率。

技术实现

  • 利用区间合并算法可以实时调整和优化时间表,合并重叠的或连续的活动区间,减少空闲时间,增加资源使用效率。

代码示例

假设有一个初步的活动时间表,需要进行优化合并。

activities = [[10, 12], [11, 13], [12, 15], [17, 19]]
# 使用区间合并算法优化活动时间表
optimized_activities = merge(activities)
print("优化后的活动时间表:", optimized_activities)

输出解析

  • 此示例中,活动时间表通过合并重叠的时间区间来优化,减少了时间段的碎片化,提高了时间资源的利用率。

总结

通过上述应用示例,我们可以看到区间合并算法不仅限于理论问题,而是可以广泛应用于实际项目中,如会议室预订系统和时间表管理等,帮助开发者和组织有效地管理和优化时间资源。这种算法的实际应用突出了它在现代编程中的实用价值和广泛适用性。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
1天前
|
算法 IDE 测试技术
Python中算法错误
【7月更文挑战第17天】
13 4
|
1天前
|
算法 计算机视觉 Python
Python并查集大揭秘:让你在算法界呼风唤雨,秒杀一切复杂场景!
【7月更文挑战第18天】并查集是Python中解决集合动态合并与查询的利器,常用于复杂问题。例如,在社交网络中快速判断用户是否在同一朋友圈,通过路径压缩优化的`UnionFind`类实现。另外,计算图像中岛屿数量也可借助并查集,将相邻像素合并成集合。并查集的应用显示了其在算法中的高效和灵活性,是提升编程技能的关键工具。
8 2
|
2天前
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
2天前
|
存储 算法 Python
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
【7月更文挑战第17天】并查集,高效解决集合合并查询问题,常用于图的连通性判断。Python实现关键包含查找和合并操作。初始化时,元素各自为集合。查找使用路径压缩优化,合并则可选按秩策略保持平衡。例如,检测无向图环路,遍历边,若并查集发现边两端已在同一集合,则存在环。掌握并查集,提升算法能力,助你在问题解决中一飞冲天!动手实践,成为算法达人!
12 2
|
8天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
6天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
14 5
|
7天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
33 4
|
8天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
8天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战