时间间隔是指由起点和终点表示的时间间隔。例如，我们可能会得到一个时间间隔 [1，10]，它的起点是 1，终点是 10。有些问题会赋予这些起点和终点整数以意义。
问题：
给定一个间隔集合，合并所有重叠的间隔。
输入：[[1,3],[5,10],[7,15],[18,30],[22,25]]
输出：[[1,3],[5,15],[18,30]]
我们得到的是一个数组的时间间隔集合。我们将单个区间作为嵌套数组。每个区间有两位数，分别代表起点和终点。由于这个特定问题没有说明这些起始/结束整数的含义，我们将起始和结束整数看作分钟。
以下是如何合并给定输入中重叠间隔的方法：
绝对地！以下是如何合并给定输入中重叠间隔的方法：
算法：
- 按起始点对间隔进行排序。这可确保以正确的顺序考虑可能重叠的间隔。
- 初始化一个空列表merged_intervals来存储合并的间隔。
- 迭代排序的区间：
- 如果当前间隔current_interval与merged_intervals中的最后一个间隔重叠（检查是否current_interval[0] <= merged_intervals[-1][1]）：
- 更新合并区间（merged_intervals）中的最后一个区间，将其终点扩展到当前终点和当前区间终点的最大值（merged_intervals[-1][1] = max(merged_intervals[-1][1],current_interval[1])）。
否则，将当前间隔作为新间隔附加到merged_intervals。
返回merged_intervals列表。
输入：[[1,3],[5,10],[7,15],[18,30],[22,25]]
1.排序间隔：[[1,3],[5,10],[7,15],[18,30],[22,25]]
2.初始化合并区间：
3.遍历区间：
- current_interval = [1,3] (与 merged_intervals 中的无重叠)
- 将 [1,3] 追加到 merged_intervals 中：[[1,3]]
- current_interval = [5,10] （与 merged_intervals 中的零重合）
- 将 [5,10] 追加到合并区间：[[1,3], [5,10]]
- current_interval = [7,15] （与 [5,10] 重叠）
- 将合并区间中的 [5,10] 更新为 [5,15]：[[1,3], [5,15]]
- current_interval = [18,30] （与合并区间中的 0 重合）
- 将 [18,30] 追加到合并区间：[[1,3], [5,15], [18,30]]
- current_interval = [22,25] （与合并区间中的零重合）
- 将 [22,25] 追加到合并区间：[[1,3], [5,15], [18,30], [22,25]]
4.返回合并区间：[[1,3], [5,15], [18,30], [22,25]]
该算法能有效合并重叠区间，由于采用了排序步骤，时间复杂度为 O(n log n)，空间复杂度为 O(n) 。
Python代码：
def merge_intervals(intervals):
if not intervals:
return []
# Sort intervals based on the start points
intervals.sort(key=lambda x: x[0])
merged_intervals = [intervals[0]]
for i in range(1, len(intervals)):
current_start, current_end = intervals<i>
last_start, last_end = merged_intervals[-1]
# 检查重叠
if current_start <= last_end:
#合并重叠区间
merged_intervals[-1] = [last_start, max(last_end, current_end)]
else:
# 添加非重叠间隔
merged_intervals.append([current_start, current_end])
return merged_intervals
# Example usage:
input_intervals = [[1, 3], [5, 10], [7, 15], [18, 30], [22, 25]]
output_intervals = merge_intervals(input_intervals)
print("Merged Intervals:", output_intervals)
|
Go代码：
package main
import (
"fmt"
"sort"
)
type Interval struct {
Start int
End int
}
func mergeIntervals(intervals []Interval) []Interval {
if len(intervals) == 0 {
return []Interval{}
}
//// 根据起始点对时间间隔进行排序
sort.Slice(intervals, func(i, j int) bool {
return intervals<i>.Start < intervals[j].Start
})
mergedIntervals := []Interval{intervals[0]}
for i := 1; i < len(intervals); i++ {
currentStart, currentEnd := intervals<i>.Start, intervals<i>.End
lastStart, lastEnd := mergedIntervals[len(mergedIntervals)-1].Start, mergedIntervals[len(mergedIntervals)-1].End
// 检查重叠是否
if currentStart <= lastEnd {
//合并重叠区间
mergedIntervals[len(mergedIntervals)-1] = Interval{Start: lastStart, End: max(lastEnd, currentEnd)}
} else {
// 添加非重叠间隔
mergedIntervals = append(mergedIntervals, Interval{Start: currentStart, End: currentEnd})
}
}
return mergedIntervals
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
inputIntervals := []Interval{{1, 3}, {5, 10}, {7, 15}, {18, 30}, {22, 25}}
outputIntervals := mergeIntervals(inputIntervals)
fmt.Println("Merged Intervals:", outputIntervals)
}
|
这个 Go 程序定义了一个 Interval 结构和一个 mergeIntervals 函数，用于合并重叠的时间间隔。主函数使用一组时间间隔样本演示了其用法。sort.Slice 函数用于根据起始点对区间进行排序。
Rust代码
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
struct Interval {
start: i32,
end: i32,
}
impl Interval {
fn new(start: i32, end: i32) -> Self {
Self { start, end }
}
}
fn merge_intervals(intervals: &mut Vec<Interval>) -> Vec<Interval> {
if intervals.is_empty() {
return Vec::new();
}
intervals.sort_by_key(|interval| interval.start);
let mut merged_intervals = vec![intervals[0]];
for i in 1..intervals.len() {
let current_start = intervals<i>.start;
let current_end = intervals<i>.end;
let last_interval = &mut merged_intervals[merged_intervals.len() - 1];
if current_start <= last_interval.end {
// 合并重叠区间
last_interval.end = last_interval.end.max(current_end);
} else {
// 添加非重叠间隔
merged_intervals.push(intervals<i>);
}
}
merged_intervals
}
fn main() {
let input_intervals = vec![
Interval::new(1, 3),
Interval::new(5, 10),
Interval::new(7, 15),
Interval::new(18, 30),
Interval::new(22, 25),
];
let mut intervals = input_intervals.clone();
let output_intervals = merge_intervals(&mut intervals);
println!("Merged Intervals: {:?}", output_intervals);
}
|
这个 Rust 程序定义了一个 Interval 结构和一个 merge_intervals 函数，用于合并重叠的区间。主函数使用一组时间间隔样本演示了其用法。使用 sort_by_key 方法根据起始点对区间进行排序。合并后的时间间隔将打印到控制台。