Planting flowers with no adjacent flower plots

 Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover 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]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

To ensure all the intervals are merged correctly, we need to short the interval by start time in ascending order in $O(n log n$ time, 

Once sorting is done, we can merge intervals through for loop in $O$ as below:

There is the solution:

	'''
	Given an array of intervals where intervals[i] = [starti, endi],
	merge all overlapping intervals, and return an array of the non-overlapping intervals
	that cover 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]]
	Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
	Example 2:
	Input: intervals = [[1,4],[4,5]]
	Output: [[1,5]]
	Explanation: Intervals [1,4] and [4,5] are considered overlapping.
	'''
	class Solution(object):
	def merge(self, intervals):
	"""
	:type intervals: List[List[int]]
	:rtype: List[List[int]]
	"""
	# sort the intervals by start time.
	intervals.sort(key= lambda x: x[0])
	result = []
	cur = None
	for i, v in enumerate(intervals):
	next = v
	if cur is None:
	cur = next
	elif self.is_overlap(cur, next) == True:
	cur[0] = min(cur[0], next[0])
	cur[1] = max(cur[1], next[1])
	else: # not overlap
	result.append(cur)
	cur = next
	if cur is not None:
	result.append(cur)
	return result
	def is_overlap(self, cur, next):
	return cur[1] >= next[0]
	# test case
	input = [[1,3],[2,6],[8,10],[15,18]]
	s = Solution()
	actual = s.merge(input)
	expected = [[1,6],[8,10],[15,18]]
	print(actual)
	print(expected)
	input = [[1,4],[4,5]]
	s = Solution()
	actual = s.merge(input)
	expected = [[1,5]]
	print(actual)
	print(expected)

view raw google_merge_intervals.py hosted with ❤ by GitHub