Leetcode 56. Merge Intervals (python+cpp)

题目

解法

python

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:# check empty caseif not intervals:return []intervals.sort(key=lambda x:x[0])# initialize the start ans end for current merging casestart = intervals[0][0]end = intervals[0][1]ans = []for i, interval in enumerate(intervals[1:]):if interval[0]<=end:end = max(end,interval[1])start = min(start,interval[0])else:ans.append([start,end])start = interval[0]end = interval[1]ans.append([start,end])return ans

改进版本，更简洁

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:# check empty caseif not intervals:return []intervals.sort(key=lambda x:x[0])# initialize the start ans end for current merging caseans = [intervals[0]]for i, interval in enumerate(intervals[1:]):if interval[0]<=ans[-1][1]:ans[-1][0] = min(interval[0],ans[-1][0])ans[-1][1] = max(interval[1],ans[-1][1])else:ans.append(interval)#ans.append([start,end])return ans

C++版本
sort函数设计lambda在C++中比较tricky，需要记住

class Solution {
    
public:static bool cmp(const vector<int>& left, const vector<int>& right){
    return left[0]<right[0] || (left[0]==right[0] && left[1]<right[1]);}vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty() || intervals[0].empty()){
    return {
    };}sort(intervals.begin(),intervals.end(),cmp);int prev_start = intervals[0][0];int prev_end = intervals[0][1];vector<vector<int>> output;for (int i=1;i<intervals.size();i++){
    if (prev_end>=intervals[i][0]){
    prev_start = min(prev_start,intervals[i][0]);prev_end = max(prev_end,intervals[i][1]);}else{
    output.push_back({
    prev_start,prev_end});prev_start = intervals[i][0];prev_end = intervals[i][1];}}output.push_back({
    prev_start,prev_end});return output;}
};