Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].Example 2:
Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
题意：把有交叉的数组合并
思路：首先按照第一列排序，然后该元素索引为i,与后面元素索引为j逐个比较，分三种情况，如果[i][1]比[j][0]小，跳过，如果[i][1]比[j][0]大，而[i][1]比[j][1]小，那么[i][1]=[j][1]，且删除[j]，然后重新判断。如果[i][1]比[j][0]大，而[i][1]比[j][1]大，说明是包含，那么删除[j]。知道i==length
class Solution(object): def merge(self, intervals): """ :type intervals: List[List[int]] :rtype: List[List[int]] """ intervals=sorted(intervals,key=lambda x:x[0]) i=0 length=len(intervals) while(1): flag=0 if(i==length): return intervals for j in range(i+1,length): if(intervals[i][1]<intervals[j][0]): pass elif(intervals[i][1]>=intervals[j][0]): if(intervals[i][1]>=intervals[j][1]): intervals.remove(intervals[j]) length-=1 flag=1 break intervals[i][1]=intervals[j][1] intervals.remove(intervals[j]) length-=1 flag=1 break if(flag==1): pass else: i+=1
