今天在LeetCode上面做了一道排序题：合并区间。该题也不算太难，先用非常暴力的方法解决了。该步骤如下：
1.初始化每一个区间的最小值min与最大值max
2.遍历所有区间，找到区间下限最小的那个，并用min，max记入。
3.删除步骤2找到的区间
4.遍历剩下的所有区间，如果该区间的最小值小于或等于步骤2中的最大值，记入该区间的最大值。
5.如果该区间的最大值大于max，那么max 就等于该最大值。
6.重复步骤4,5若干次，并在结束后删除所有符合步骤4的区间，添加【min,max】为合并后的区间
7.但剩下的区间数大于零时，重复操作上述过程
def merge(self, intervals: List[List[int]]) -> List[List[int]]: lists = [] while (len(intervals)>0): min = 100000 index = 0 for a in range(len(intervals)): if min> intervals[a][0]: min = intervals[a][0] max = intervals[a][1] index = a intervals.remove(intervals[index]) n = 10 while(n): re = [] for a in range(len(intervals)): if max >= intervals[a][0]: if max <= intervals[a][1]: max = intervals[a][1] re.append(intervals[a]) n -= 1 intervals = [a for a in intervals if a not in re] lists.append([min,max]) return lists
上述操作没有涉及的如何算法的思想，下面让我们在用另外一种操作，先按区间的最小值排好序，然后再遍历。排序后可以合并的区间是连续的，这样就省去了上面的步骤6的重复操作4,5，从而提高了程序的效率。
具体步骤就不写了，基本与上面的相似。
def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) merges = [] for a in intervals: if not merges or merges[-1][-1] < a[0]: merges.append(a) else: if merges[-1][-1] < a[-1]: merges[-1][-1] = a[-1] return merges
Thank for your time !!
ps: 参考LeetCode官方解析。
公众号：FPGA之旅
