题解 | 合并区间

1、解题思路

1. 排序区间 ：首先将区间按照起点升序排列，这样便于后续的合并操作。
2. 合并区间 ：使用一个结果列表来存储合并后的区间。遍历排序后的区间列表，比较当前区间与结果列表中最后一个区间是否有重叠。如果有重叠，合并它们；如果没有重叠，直接将当前区间加入结果列表。

2、代码实现

C++

/**
 * struct Interval {
 *  int start;
 *  int end;
 *  Interval(int s, int e) : start(start), end(e) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类vector
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        // write code here
        if (intervals.empty()) {
            return {};
        }

        // 按照区间起点升序排序
        sort(intervals.begin(), intervals.end(), [](const Interval & a,
        const Interval & b) {
            return a.start < b.start;
        });

        vector<Interval> result;
        result.push_back(intervals[0]);

        for (int i = 1; i < intervals.size(); ++i) {
            Interval& last = result.back();
            if (intervals[i].start <= last.end) {
                // 合并区间
                last.end = max(last.end, intervals[i].end);
            } else {
                // 添加到结果列表
                result.push_back(intervals[i]);
            }
        }

        return result;
    }
};

Java

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类ArrayList
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // write code here
        if (intervals == null || intervals.size() == 0) {
            return new ArrayList<Interval>();
        }

        // 按照区间起点升序排序
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });

        ArrayList<Interval> result = new ArrayList<Interval>();
        result.add(intervals.get(0));

        for (int i = 1; i < intervals.size(); ++i) {
            Interval last = result.get(result.size() - 1);
            if (intervals.get(i).start <= last.end) {
                // 合并区间
                last.end = Math.max(last.end, intervals.get(i).end);
            } else {
                // 添加到结果列表
                result.add(intervals.get(i));
            }
        }

        return result;
    }
}

Python

# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param intervals Interval类一维数组 
# @return Interval类一维数组
#
class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        # write code here
        if not intervals:
            return []
        
        # 按照区间起点升序排序
        intervals.sort(key=lambda x: x.start)
        
        result = [intervals[0]]
        
        for interval in intervals[1:]:
            last = result[-1]
            if interval.start <= last.end:
                # 合并区间
                last.end = max(last.end, interval.end)
            else:
                # 添加到结果列表
                result.append(interval)
        
        return result

3、复杂度分析

1. 排序区间：首先将区间按照起点升序排序，这样便于后续的合并操作。
2. 合并区间：使用一个结果列表来存储合并后的区间。遍历排序后的区间列表，比较当前区间与结果列表中最后一个区间是否有重叠。如果有重叠，合并它们；如果没有重叠，直接将当前区间加入结果列表。
3. 时间复杂度：排序的时间复杂度为O(nlogn)，合并的时间复杂度为O(n)，因此总的时间复杂度为O(nlogn)。
4. 空间复杂度：结果列表的空间复杂度为O(n)，排序的空间复杂度为O(logn)（取决于排序算法），因此总的空间复杂度为O(n)。