# greedy (myway and neetcode)
    # - time: O(n)
    # - space: O(1), 除了存储返回答案的空间以外，我们只需要额外的常数空间即可。
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """

        res = []
        for i, interval in enumerate(intervals):
            if newInterval[1] < interval[0]:  # no overlapping, and newInterval is on the left of the cur interval
                res.append(newInterval)
                res.extend(intervals[i:])
                return res  # 这时候不需要再 for loop 了，因为题目保证了 intervals 是排好序的
            elif 
            else:
                # has intersection, and not insert into res yet
                newInterval = [min(newInterval[0], interval[0]), max(newInterval[1], interval[1])]

        res.append(newInterval)  # edge case: intervals 中无元素
        return res

# approach 1 - myself
# - time: O(nlogn)
# - space: O(1)
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        # sort, or intervals.sort(key=lambda pair: pair[0])
        intervals.sort()  # time: O(logn)

        res = []
        newInterval = intervals[0]
        for i in range(1, len(intervals)):  # time: O(n)
            interval = intervals[i]
            if newInterval[1] < interval[0]:  # no overlapping, and newInterval is on the left side of interval
                res.append(newInterval)
                newInterval = interval
            else:
                newInterval = [min(newInterval[0], interval[0]), max(newInterval[1], interval[1])]

        res.append(newInterval)
        return res
      

# approach 2 - neetcode, quite similar
# - 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 interval[0] <= lastEnd:  # has overlap between the current interval and the previous added interval
				res[-1][1] = max(lastEnd, interval[1])  # merge "end"
			else:  # no overlap
				res.append(interval)
		return res

# Greedy (Sort By Start) - myself
    # time: O(nlogn)
    # space: O(1) or O(n) depending on the sorting algorithm.
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        # sort
        intervals.sort()

        res = 0
        preInterval = intervals[0]
        for i in range(1, len(intervals)):
            interval = intervals[i]
            if preInterval[1] <= interval[0]:  # no overlapping
                preInterval = interval  # because if no overlapping, interval's start is >= than preInterval's end
            else:  # overlapping
                if interval[1] < preInterval[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)
                    preInterval = interval
                res += 1

        return res
        
# Greedy (Sort By Start) - leetcode
	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
    #   - 按 start 排序 intervals 之后，
    #      - 如果后一个 interval 的 start 在 前一个 interval 的 end 之后，则必须要多用一只 arrow
    #      - 如果后一个 interval 的 start 在 前一个 interval 的 end 之前，则取两者的 end 的最小值，作为发 arrow 的位置（因为其是同时能命中这两个 interval 的发 arrow 的最大值，as in 有最大的可能能覆盖后续的 interval）
    #   - time: O(nlog)
    #   - space: O(1) or O(n) depending on the sorting algorithm
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        points.sort()  # points.sort(key=lambda i: i[0]), sort by first, ACS, time: O(nlogn)

        totalArrowCount = 1
        curMaxArrowPosition = points[0][1]
        for i in range(1, len(points)):  # time: O(n)
            point = points[i]
            if curMaxArrowPosition < point[0]:  # no overlapping, and thus have to use one more arrow
                totalArrowCount += 1
                curMaxArrowPosition = point[1]
            else:  # has overlapping, update curMaxArrowPosition with the max value without using a new arrow
                curMaxArrowPosition = min(curMaxArrowPosition, point[1])
        return totalArrowCount

	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

# sort
#    time: O(nlogn)
#    space: O(1) or  O(n) depending on the sorting algorithm.
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
        intervals.sort(key=lambda i: i.start)

        for i in range(1, len(intervals)):
            i1 = intervals[i - 1]
            i2 = intervals[i]

            if i1.end > i2.start:
                return False
        return True

class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: the minimum number of conference rooms required
    """

    # sort
    #  - time: O(nlogn)
    #  - space: O(n)
    def min_meeting_rooms(self, intervals: List[Interval]) -> int:
        # Write your code here
        starts, ends = [], []  # space: O(n) # O(2n)
        for interval in intervals:
            starts.append(interval.start)
            ends.append(interval.end)
        # time: O(nlogn) # O(2nlogn)
        starts.sort()
        ends.sort()

        res = 0
        count = 0
        startIdx, endIdx = 0, 0
        while startIdx < len(starts):  # time: O(n)
            if starts[startIdx] < ends[endIdx]:
                count += 1
                res = max(res, count)
                startIdx += 1
            else:
                endIdx += 1
                count -= 1

        return res
# todo，看看其他解法