Intervals

# Time complexity: O(n)
# Space complexity: O(1) excluding output
def summaryRanges(nums: List[int]) -> List[str]:
    result = []
    i = 0

    while i < len(nums):
        # Get consecutive range
        end = i
        while end + 1 < len(nums) and nums[end] + 1 == nums[end + 1]:
            end += 1
        # If equal, range did not expand
        if end > i:
            result.append(str(nums[i]) + "->" + str(nums[end]))
        else:
            result.append(str(nums[i]))
        i = end + 1

    return result

# Time complexity: O(n * log(n))
# Space complexity: O(1) excluding output
def merge(intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    answer = []
    curr = intervals[0]

    for pair in intervals:
        if pair[0] <= curr[1]:
            curr[1] = max(pair[1], curr[1])
        else:
            answer.append(curr)
            curr = pair
    answer.append(curr)
    return answer

# Time complexity: O(n)
# Space complexity: O(1) excluding output
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    answer = []

    # Add non-overlapping intervals
    i = 0
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        answer.append(intervals[i])
        i += 1

    # Merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    answer.append(newInterval)

    # Add remaining intervals
    while i < len(intervals):
        answer.append(intervals[i])
        i += 1

    return answer

# Time complexity: O(n * log(n))
# Space complexity: O(1)
def findMinArrowShots(self, points: List[List[int]]) -> int:
    # Sort by x<end>
    points.sort(key=lambda x: x[1])
    count = 1
    currIdx = 0

    # Shoot arrow at end of leftmost unpopped balloon
    for i in range(1, len(points)):
        # Skip all balloons that will be popped by current arrow
        if points[i][0] <= points[currIdx][1]:
            continue
        count += 1
        currIdx = i

    return count