我们得到的是一个数组的时间间隔集合。我们将单个区间作为嵌套数组。每个区间有两位数,分别代表起点和终点。由于这个特定问题没有说明这些起始/结束整数的含义,我们将起始和结束整数看作分钟。
返回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 方法根据起始点对区间进行排序。合并后的时间间隔将打印到控制台。