Merge interval, linked list, array

In array  intervals  Represents a set of intervals , The single interval is  intervals[i] = [starti, endi] . Please merge all overlapping intervals , And return a non overlapping interval array , The array needs to cover exactly all the intervals in the input .

 

Example 1：

Input ：intervals = [[1,3],[2,6],[8,10],[15,18]]
Output ：[[1,6],[8,10],[15,18]]
explain ： Section [1,3] and [2,6] overlap , Combine them into [1,6].

Example  2：

Input ：intervals = [[1,4],[4,5]]
Output ：[[1,5]]
explain ： Section [1,4] and [4,5] Can be regarded as overlapping interval .

# Merge range 

def sortIntervals(intervals):			# Write function   Insertion sort 
	for i in range(1,len(intervals)):
		for j in range(i):
			if intervals[i][0]<intervals[j][0]:
				tmp=intervals[i]
				del intervals[i]
				intervals.insert(j,tmp)
	return intervals

def merge(intervals):					# Write function , Merge range 
	sortIntervals(intervals)			# The first step is to sort, That is to give intervals Sort 
	for i in range(1,len(intervals)):	# The second step is to merge , And use 【0,0】 placeholder 
		if intervals[i][0] <= intervals[i-1][1]:
			intervals[i-1][1]=intervals[i][1]
			intervals[i]=[0,0]
	while True:							# The third step   Delete 【0,0】
		if [0,0] in intervals:
			intervals.remove([0,0])
		else:
			break
	return intervals

print(merge([[1,3],[8,10],[2,6],[15,18]]))
print(merge([[1,4],[4,5]]))
print(merge([[1,4],[4,5],[6,12],[11,15]]))

Insertion sort

【0,0】 placeholder

remove Method