# approach 1 - elegent way (neetcode)
# - time: O(nlogn)
# - space: O(1)
	def merge(self, intervals: List[List[int]]) -> List[List[int]]:
		intervals.sort(key=lambda pair: pair[0])

		res = [intervals[0]]
		for i in range(1, len(intervals)):
			interval = intervals[i]

			lastEnd = res[-1][1]
			if lastEnd >= interval[0]:  # has overlap between the current interval and the previous added interval
				res[-1][1] = max(lastEnd, interval[1])  # merge
			else:  # not has overlap
				res.append(interval)
		return res

# approach 2 - my way
# - time: O(nlogn)
# - space: O(1)
	def merge(self, intervals: List[List[int]]) -> List[List[int]]:
		if len(intervals) == 1:
			return intervals

		intervals.sort(key=lambda pair: pair[0])
		res = []
		tempInterval = intervals[0]
		for i in range(1, len(intervals)):
			interval = intervals[i]

			if tempInterval[1] < interval[0]:
				res.append(tempInterval)
				tempInterval = [interval[0], interval[1]]
			elif interval[1] < tempInterval[0]:
				res.append(interval)
			else:
				tempInterval = [min(tempInterval[0], interval[0]), max(tempInterval[1], interval[1])]

		res.append(tempInterval)
		return res

# approach 1 - elegent way (neetcode)
# - time: O(n)
# - space: O(1), 除了存储返回答案的空间以外，我们只需要额外的常数空间即可。
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
		res = []
		for idx in range(len(intervals)):
			interval = intervals[idx]
			if newInterval[1] < interval[0]:  # no overlapping, and newInterval is on the left of the cur interval
				res.append(newInterval)
				return res + intervals[idx:]
			elif newInterval[0] > interval[1]:  # no overlapping, and newInterval is on the right of the cur interval
				res.append(intervals[idx])
			else:  # has overlapping
				newInterval = [min(newInterval[0], interval[0]),
							   max(newInterval[1], interval[1])]  # not insert into res yet

		res.append(newInterval)
		return res
  

# approach 2 - non-elegent way
# - time: O(n)
# - space: O(1), 除了存储返回答案的空间以外，我们只需要额外的常数空间即可。
	def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
		res = []
		merged = False
		for interval in intervals:
			start, end = interval[0], interval[1]
			if merged:
				if res[-1][1] < start:
					res.append(interval)
				else:
					res[-1][1] = max(end, res[-1][1])
				continue

			# not merged yet
			if newInterval[1] < start:  # no overlap
				res.append(newInterval)
				res.append(interval)
				merged = True
			elif newInterval[0] > end:  # no overlap
				res.append(interval)
			else:  # has overlap
				res.append([min(newInterval[0], start), max(newInterval[1], end)])
				merged = True

		if not merged:
			res.append(newInterval)
		return res

# Version 1
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
		res = 0
		intervals.sort(key=lambda i: i[0])
		prev_interval = intervals[0]
		for i in range(1, len(intervals)):
			cur_interval = intervals[i]
			if cur_interval[0] < prev_interval[1]:  # overlapping
				res += 1
				if cur_interval[1] < prev_interval[
					1]:  # remove the interval that ends with a larger value,
					## because if we have [[1,2], [1,3], [2,3], [3,4]], we could remove [1, 3], instead of [1, 2], so that we only need to remove 1 interval (instead of 2 intervals)
					prev_interval = cur_interval
			else:  # no overlapping
				prev_interval = cur_interval # because if no overlapping, cur_interval's end is >= than prev_interval's end
        
# Version 2
	def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
		intervals.sort(key=lambda i: i[0])

		res = 0
		prev_end = intervals[0][1]
		for i in range(1, len(intervals)):
			cur_interval = intervals[i]
			if cur_interval[0] < prev_end:  # overlapping
				# remove the interval that ends with a larger value,
				## because if we have [[1,2], [1,3], [2,3], [3,4]], we could remove [1, 3], instead of [1, 2], so that we only need to remove 1 interval (instead of 2 intervals)
				res += 1
				prev_end = min(prev_end, cur_interval[1])
			else:  # no overlapping
				# because if no overlapping, cur_interval's end is >= than prev_interval's end
				prev_end = cur_interval[1]

		return res

# sort by end
	def findMinArrowShots(self, points: List[List[int]]) -> int:
		points.sort(key=lambda i: i[1])  # sort by end, e.g., the result will be [[0,9], [2, 9], [9, 10], [7, 12]]
		# Then, the end of the next element will be >= the end of the current element

		arrows = 1  # we need to cost 1
		cur_arrow_position = points[0][1]
		for i in range(1, len(points)):
			point = points[i]
			start, end = point[0], point[1]
			if start > cur_arrow_position:  # no intersection, thus we have to spend a more arrow
				arrows += 1
				cur_arrow_position = end
		return arrows
  
# sort by start
	def findMinArrowShots(self, points: List[List[int]]) -> int:
		points.sort(key=lambda i: i[0])  # sort by first

		arrows = 1
		cur_arrow_position = points[-1][0]
		for i in range(len(points) - 2, -1, -1):
			point = points[i]
			start, end = point[0], point[1]
			if end < cur_arrow_position:
				arrows += 1
				cur_arrow_position = start
		return arrows

	def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
		hasX = False
		hasY = False
		hasZ = False
		for triplet in triplets:
			if triplet[0] > target[0] or triplet[1] > target[1] or triplet[2] > target[
				2]:  # Not consider such a triplet, since any of elements of this triplet is > than the corrsponding element in the target array, we shouldn't consider this triplet, otherwise, we cannot form target if we use this triplet, e.g., triplet: [2,8,3] target: [2,7,3] -> the final triplet will be [x,8,x]
				continue

			# Then, for all triplets come to here, the element will <= the element of the target, and if = for all three elements, we are sure that we can make it somehow
			if triplet[0] == target[0]:
				hasX = True
			if triplet[1] == target[1]:
				hasY = True
			if triplet[2] == target[2]:
				hasZ = True

		return hasX and hasY and hasZ