作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
给出一个无重叠的，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表仍然按照区间起始端点有序且不重叠（如果有必要的话，可以合并区间）。
输入格式
- intervals：一个二维数组，每个内部数组包含两个整数，表示一个区间的起始和结束位置。
- newInterval：一个包含两个整数的数组，表示需要插入的新区间的起始和结束位置。
输出格式
- 返回一个二维整数数组，表示合并后的区间。
示例
示例 1
输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]]
示例 2
输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 新区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
方法一：直接合并
解题步骤
- 添加新区间：将新区间添加到区间列表中。
- 排序：按每个区间的起始位置进行排序。
- 合并区间：使用一个循环遍历排序后的区间列表，合并所有重叠的区间。
完整的规范代码
def insert(intervals, newInterval): """ 直接合并新区间 :param intervals: List[List[int]], 输入的区间列表 :param newInterval: List[int], 需要插入的新区间 :return: List[List[int]], 合并后的区间列表 """ intervals.append(newInterval) 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(insert([[1,3],[6,9]], [2,5])) # 输出: [[1,5],[6,9]] print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])) # 输出: [[1,2],[3,10],[12,16]]
算法分析
- 时间复杂度：(O(n log n))，主要耗时操作是排序。
- 空间复杂度：(O(n))，存储合并后的区间。
方法二：优化的插入合并
解题步骤
- 找到插入位置：遍历区间列表，找到新区间的正确插入位置。
- 合并区间：在插入位置处合并新区间，如果新区间与现有区间重叠，进行合并处理。
- 构建最终结果：将处理后的区间重新组装成结果列表。
完整的规范代码
def insert(intervals, newInterval): """ 优化的插入合并方法 :param intervals: List[List[int]], 输入的区间列表 :param newInterval: List[int], 需要插入的新区间 :return: List[List[int]], 合并后的区间列表 """ merged, i = [], 0 start, end = newInterval[0], newInterval[1] # 添加所有结束时间小于新区间开始时间的区间 while i < len(intervals) and intervals[i][1] < start: merged.append(intervals[i]) i += 1 # 合并所有与新区间重叠的区间 while i < len(intervals) and intervals[i][0] <= end: start = min(start, intervals[i][0]) end = max(end, intervals[i][1]) i += 1 merged.append([start, end]) # 添加剩余区间 while i < len(intervals): merged.append(intervals[i]) i += 1 return merged # 示例调用 print(insert([[1,3],[6,9]], [2,5])) # 输出: [[1,5],[6,9]] print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])) # 输出: [[1,2],[3,10],[12,16]]
算法分析
- 时间复杂度：(O(n))，其中
n是区间的数量，最坏情况下需要遍历所有区间。 - 空间复杂度：(O(n))，用于存储合并后的区间。
方法三：二分查找插入位置
此方法使用二分查找来确定新区间插入的位置，以减少查找时间，然后使用类似方法二的方式进行区间合并。
解题步骤
- 二分查找：使用二分查找确定新区间插入的位置。
- 合并区间：在找到的位置处插入新区间，并执行合并操作。
- 构建结果：按照合并逻辑构建最终的区间列表。
完整的规范代码
def insert(intervals, newInterval): """ 使用二分查找优化插入位置的确定 :param intervals: List[List[int]], 输入的区间列表 :param newInterval: List[int], 需要插入的新区间 :return: List[List[int]], 合并后的区间列表 """ low, high = 0, len(intervals) - 1 while low <= high: mid = (low + high) // 2 if intervals[mid][1] < newInterval[0]: low = mid + 1 elif intervals[mid][0] > newInterval[1]: high = mid - 1 else: newInterval = [min(intervals[mid][0], newInterval[0]), max(intervals[mid][1], newInterval[1])] intervals.pop(mid) return insert(intervals, newInterval) intervals.insert(low, newInterval) return intervals # 示例调用 print(insert([[1,3],[6,9]], [2,5])) # 输出: [[1,5],[6,9]] print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])) # 输出: [[1,2],[3,10],[12,16]]
算法分析
- 时间复杂度：(O(n log n))，二分查找 (O(log n)) 加上最坏情况下的合并操作 (O(n))。
- 空间复杂度：(O(n))，用于存储合并后的区间。
方法四：利用堆结构优化
尽管这方法在合并区间问题中不是最常用的方法，它主要用于处理实时数据流中的区间合并问题。我们暂时跳过此方法的具体实现。
方法五：利用线段树优化
此方法主要用于处理大规模数据集中的动态区间查询和更新问题，因复杂度较高，在此场景下并不常用，暂不展开。
不同算法的优劣势对比
| 特征 | 方法一: 直接合并 | 方法二: 优化合并 | 方法三: 二分查找插入 | 方法四: 利用堆结构 | 方法五: 线段树 |
| 时间复杂度 | (O(n log n)) | (O(n)) | (O(n log n)) | (O(n log n)) | (O(log n)) |
| 空间复杂度 | (O(n)) | (O(n)) | (O(n)) | (O(n)) | (O(n)) |
| 优势 | 简单直观 | 高效，适合大部分场景 | 查找效率高 | 实时处理优化 | 动态更新优化 |
| 劣势 | 效率不是最优 | 需要手动处理边界 | 实现复杂 | 空间复杂度高 | 实现复杂度高 |
应用示例详解：事件日程管理系统
场景描述
在公司或社区的事件日程管理中，管理员需要添加和更新活动的时间，同时确保没有时间上的冲突。这些活动可能包括会议、研讨会、社区聚会等，每个活动都有明确的开始和结束时间。有效的时间管理不仅可以优化资源使用，还能提高参与者的满意度。
技术实现
使用区间插入和合并算法可以帮助系统管理员高效地管理和调整日程安排，以下是具体的实现方法和步骤：
方法：优化的插入合并
技术选择：
选择方法二（优化的插入合并），因为它直接在原有区间列表上操作，避免了排序的开销，且在实际应用中能快速响应日程变动。
实现步骤：
- 初始化日程列表：开始时，日程列表为空或已有一些预设活动。
- 插入新活动：每次有新活动（新区间）加入时，根据该活动的开始和结束时间插入并尝试合并。
- 合并处理：插入新区间后，检查并合并任何重叠的区间。
- 更新日程：合并完成后，更新日程列表，保持列表中的区间始终无重叠且有序。
代码实现：
def insert(intervals, newInterval): """ 优化的插入合并方法，适用于日程管理 :param intervals: List[List[int]], 现有的区间列表（活动日程） :param newInterval: List[int], 新活动的区间 :return: List[List[int]], 更新后的区间列表 """ merged = [] i, n = 0, len(intervals) # 处理所有在新区间前结束的区间 while i < n and intervals[i][1] < newInterval[0]: merged.append(intervals[i]) i += 1 # 合并所有与新区间重叠的区间 while i < n and intervals[i][0] <= newInterval[1]: newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])] i += 1 merged.append(newInterval) # 添加剩余的区间 while i < n: merged.append(intervals[i]) i += 1 return merged # 示例日程 existing_events = [[9, 12], [13, 16]] new_event = [12, 14] # 日程更新 updated_events = insert(existing_events, new_event) print("Updated event schedule:", updated_events)
输出解释：
- 程序首先将新活动尝试与现有活动合并。
- 如果新活动时间与现有活动重叠或连续，它们会被合并为一个活动，从而优化空间利用并避免冲突。
应用优势
- 高效性：直接操作，避免不必要的数据处理，响应速度快。
- 准确性：确保日程中活动的时间不会重叠，避免资源冲突。
- 灵活性：方便对日程进行动态调整，满足突发事件的处理需求。
总结
通过在事件日程管理系统中应用区间合并算法，管理员可以更有效地处理和更新日程安排，确保所有活动都能顺利进行而不互相冲突。这种方法不仅提升了管理效率，还增强了系统对于变动的适应能力，是现代大规模活动管理中不可或缺的技术手段。
欢迎关注微信公众号 数据分析螺丝钉
