每日一道算法题 合并区间

题目

合并区间_牛客题霸_牛客网 (nowcoder.com)

可以先看Python。

C语言

#include <stdlib.h>
/*** struct Interval {*	int start;*	int end;* };*/
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param intervals Interval类一维数组 * @param intervalsLen int intervals数组长度* @return Interval类一维数组* @return int* returnSize 返回数组行数*/
//
int cmp(const void *before,const void *after)
{int b=((struct Interval*)before)->start;int a= ((struct Interval*)after)->start;return b-a;
}struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {// write code hereint i;//循环用int step=1;//步长int return_len=intervalsLen;//排序qsort(intervals,intervalsLen,sizeof(struct Interval),cmp);//i从1开始for(i=1;i<intervalsLen;i++)// intervals[i]表示后面的元素//intervals[i-step] 前面待合并的元素if(intervals[i].end<=intervals[i-step].end){step++;return_len--;}else if(intervals[i].start<=intervals[i-step].end){intervals[i-step].end=intervals[i].end;step++;return_len--;}else{intervals[i-step+1].start = intervals[i].start;intervals[i-step+1].end = intervals[i].end;}*returnSize=return_len;return intervals;
}

C++

/*** struct Interval {*	int start;*	int end;*	Interval(int s, int e) : start(start), end(e) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param intervals Interval类vector * @return Interval类vector*/vector<Interval> merge(vector<Interval>& intervals) {// write code here//排序，按start升序，start同，按end降序。匿名函数sort(intervals.begin(),intervals.end(),[](Interval before,Interval after){if(before.start==after.start) return before.end>after.end;else return before.start<after.start;});vector<Interval> ans;for(int _=0;_<intervals.size();_++)if(ans.empty()||ans.back().end<intervals[_].start)ans.push_back(intervals[_]);elseif(ans.back().end<intervals[_].end) ans.back().end=intervals[_].end;return ans;}
};

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]:ans=[]if not intervals: return []# 按start排序intervals.sort(key=lambda x:x.start)# print(intervals)s=intervals[0].starte=intervals[0].end
# [[10,30],[20,60],[80,100],[150,180]]
# [[10,30],[20,60],[80,100],[90,180]]for _ in range(1,len(intervals)):cur=intervals[_]if cur.start<=e:e=max(e,cur.end)else:ans.append(Interval(s,e))s=cur.starte=cur.endans.append(Interval(s,e))return ans