def wow!(n: int) -> int:

        return n+1

    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        
        # Interval Insertion / Greedy Merge:
        # We are inserting a new interval into a list of non-overlapping, sorted intervals
        # and returning a merged list of non-overlapping intervals.

        # Greedy Merge Idea:
        # 1. Intervals ending before the new interval -> no overlap, add directly
        # 2. Intervals overlapping with new interval -> merge into one
        # 3. Intervals starting after the new interval ends -> add directly
        # We iterate once over all intervals, maintaining a merged interval along the way.

        # num of intervals
        # sc: O(1)
        n = len(intervals)

        # sc: list of n intervals O(n)
        res = []

        # new interval to be added
        # sc: O(1)
        start = newInterval[0]
        end = newInterval[1]

        # iterate over list of sorted intervals
        # sc: O(1)
        i = 0

        # Base Case: intervals before newInterval
        # Check: interval_end < newInterval_start 
        # Then: append to new list
        # tc: O(n)
        while i < n and intervals[i][1] < start:

            # simply add interval
            res.append(intervals[i])

            # iterate to next interval
            i += 1

        # Merge Case: interval overlaps with newInterval
        # Check: Interval overlaps
        # Then: merge into interval + newInterval
        # tc: O(n)
        while i < n and intervals[i][0] <= end:

            # Determine new start and end of merged interval

            # update start to be min between interval and newInterval
            start = min(start, intervals[i][0])
            # update end to be max between interval and newInterval
            end = max(end, intervals[i][1])

            # iterate to next interval
            i += 1

        # Append merged interval
        res.append([start, end])

        # Base Case: intervals after newInterval
        # Check: newInterval_end < interval_star
        # Then: append to new list
        # tc: O(n)
        while i < n:

            # simply add interval
            res.append(intervals[i])

            # iterate to next interval
            i += 1

        # overall: tc O(n)
        # overall: sc O(1)
        return res

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        # Interval Merging / Greedy + Sorting:
        # Goal: merge all overlapping intervals into a list of non-overlapping intervals

        # This is the same as Merge Intervals, just that the list is not sorted
        # and the intervals may overlap

        # Linear Greedy Scan:
        # The current greedy merge works because intervals are sorted by start time.
        # The properties of the intervals sorted by start time, allow us to assume:
        #   - All previous intervals have already been merged into merged[-1], the last interval
        #   - No earlier intervals can overlap the current interval
        #   - Two possibilities exist for the current interval
        #       - Overlaps with merged[-1] => merge by updated the end
        #       - No overlap with merged[-1] => append as new interval

        # Key Idea (Sort + Greedy Linear Scan):
        # 1. Process Root -> sort intervals by start time
        # 2. Build -> iterate through sorted intervals, merging overlapping ones
        # 3. Explore Choices -> if current interval overlaps previous (last interval in merged list), 
        #    merge then; else, append as a new last interval

        # Empty check: no intervals, return []
        if not intervals:
            return []

        # Sort intervals by start time
        # tc: python (2.3-3.10) TimSort, Python (3.11+) PowerSort Worst/Avg: O(n log n), Best: O(n)
        # sc: sorts in place, no extra memory O(1)
        intervals.sort(key=lambda x: x[0])

        # Initialize merged list with lowest start time interval,
        # at the top of the minHeap
        # tc: O(1)
        merged = [intervals[0]]

        # tc: terate over all intervals O(n)
        for i in range(1, len(intervals)):

            # Current interval
            current = intervals[i]

            # rightmost interval
            last_merged = merged[-1]

            # Current interval either:
            #   - does overlap with last interval on the merged list
            #   - does not overlap with last interval on the merged list

            # if intervals overlap, merge by updated the end time
            if current[0] <= last_merged[1]:
                last_merged[1] = max(last_merged[1], current[1])

            # no overlap, append new interval to merged list
            else:
                merged.append(current)

        # overall: tc O(n log n)
        # overall: sc O(n)
        return merged 

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        # Interval Merging / Greedy + Heap:
        # Goal: merge all overlapping intervals into a list of non-overlapping intervals

        # Linear Greedy Scan:
        # The current greedy merge works because intervals are sorted by start time.
        # The properties of the intervals sorted by start time, allow us to assume:
        #   - All previous intervals have already been merged into merged[-1], the last interval
        #   - No earlier intervals can overlap the current interval
        #   - Two possibilities exist for the current interval
        #       - Overlaps with merged[-1] => merge by updated the end
        #       - No overlap with merged[-1] => append as new interval

        # MinHeap / Priority Queue
        # Maintains a binary heap where the smallest element is at the root.
        # Allows for efficient access to the minimum element
        #   - Insertion(): parent less than or equal to children
        #   - Pop(): restructures heap to keep new min at top
        #   - Push()
        #       - New element < current top => bubble up to maintain heap property
        #       - New element >= current top => placed in proper position via bubble up
        # Guarantees root has current min with O(1) access and insertion/removal in O(log n)

        # Heapify vs Sequential Insertions
        # A heap can be build in two ways:
        #
        #   1. Sequential Insertions:
        #       - pushes n elements one by one, each in O(log k) => O(n log n)
        #
        #   2. Heapify (bottom-up):
        #       - adjusts n elements at once starting from the last parent up to the root
        #       - lower levels require fewer comparisons, so total work => O(n)

        # Key Idea (Greedy + Heap):
        # 1. Push all intervals into a min-heap ordered by start time
        # 2. Pop intervals one by one
        # 3. Explore Choices:
        #      - If no overlap with last interval in result, append
        #      - If overlap, merge intervals
        # 4. Result -> list of merged intervals

        # Empty check: no intervals, return []
        if not intervals:
            return []

        # Sort Intervals By Start Time:
        # Push all intervals into a minHeap (ordered by start)
        # tc: heapify O(n)
        # sc: n intervals in heap O(n)
        heap = [(s, e) for s, e in intervals]
        heapq.heapify(heap)

        # final interval list
        # sc: O(n)
        merged = []

        # Pop intervals one by one from low start to high start time
        # tc: n removals in log n leading to O(n log n) 
        while heap:

            # Grab interval with lowest start time
            # tc: O(log n)
            start, end = heapq.heappop(heap)

            # Current interval either:
            #   - does overlap with last interval on the merged list
            #   - does not overlap with last interval on the merged list

            # if intervals overlap, merge by updated the end time
            if not merged or merged[-1][1] < start:
                merged.append([start, end])

            # no overlap, append new interval to merged list
            else:
                merged[-1][1] = max(merged[-1][1], end)

        # overall: tc O(n log n)
        # overall: sc O(n)
        return merged

    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        
        # Note:
        # Greedy / Sorting approach
        # 0. Empty or single interval: no removals needed
        # 1. Sort intervals by end time
        # 2. Track end of last kept interval
        # 3. Iterate through intervals
        # 4. If current interval overlaps last, remove it
        # 5. If no overlap, update end to end of new interval
        # Result -> count of removed intervals

        # Empty check
        if not intervals:
            return 0

        # Sort intervals by end time (earliest finishing first)
        intervals.sort(key=lambda x: x[1])

        # Track end of first interval
        end = intervals[0][1]
        
        removals = 0

        # Iterate over intervals
        for i in range(1, len(intervals)):

            # curr interval
            start_i, end_i = intervals[i]

            # Interval overlaps -> remove
            if start_i < end:
                removals += 1

            # No overlap -> update end to current interval end
            else:
                end = end_i

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return removals

    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        
        # Note:
        # Greedy / Sorting approach
        # 0. Empty or single interval: no removals needed
        # 1. Sort intervals by start time
        # 2. Track end of last kept interval
        # 3. Iterate through intervals
        # 4. Overlap with last, keep the interval with smaller end
        # 5. No overlap, update end to end of new interval
        # Result -> count of removed intervals

        # sort
        intervals.sort()
        
        res = 0

        # end of first interval
        prevEnd = intervals[0][1]

        # Iterate over intervals
        for start, end in intervals[1:]:

            # no overlap -> update prevEnd
            if start >= prevEnd:
                prevEnd = end

            # overlap -> remove one interval, keep the one with smaller end
            else:
                res += 1
                prevEnd = min(end, prevEnd)

        # overall: time complexity
        # overall: space complexity 
        return res

    def canAttendMeetings(self, intervals: List[Interval]) -> bool:
        
        # Note:
        # 1. Sort intervals by start time
        # 2. Iterate through sorted intervals
        # 3. Curr meeting starts before previous -> conflict
        # Result -> Check if conflict exists
        
        # Empty Check
        if not intervals:
            return True

        # Sort intervals by start time
        intervals.sort(key=lambda x: x.start)

        # Iterate through sorted intervals
        for i in range(1, len(intervals)):

            # Curr meeting starts before previous -> conflict
            if intervals[i].start < intervals[i-1].end:
                return False

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return True

    def minMeetingRooms(self, intervals: List[Interval]) -> int:
        
        # Note:
        # Greedy Min-Heap
        # 1. Sort intervals by start time
        # 2. MinHeap to track meeting end times
        # 3. Iterate over intervals:
        #    Curr starts after earliest ending -> reuse room (pop heap)
        #    Curr starts before earliest ending -> new room needed, push curr end time to heap
        # Result -> size of heap at end = min rooms required

        # Empty Check
        if not intervals:
            return 0

        # Sort intervals by start time
        intervals.sort(key=lambda x: x.start)

        # MinHeap to track meeting end times
        heap = []

        for interval in intervals:

            # Curr starts after earliest ending -> reuse room (pop heap)
            if heap and interval.start >= heap[0]:
                heapq.heappop(heap)

            # Curr starts before earliest ending -> new room needed, push curr end time to heap
            heapq.heappush(heap, interval.end)

        # size of heap at end = min rooms required
        res = len(heap)
        
        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return res

    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        
        # Note:
        # Uses sorted queries with indices for mapping results.

        # Note:
        # Greedy + Min-Heap
        # 1. Sort intervals by start
        # 2. Sort queries with original indices
        # 3. Iterate queries in ascending order
        # 4. Intervals <= query -> push to heap
        # 5. Intervals > query -> pop
        # 6. record result
        # Result -> top of heap is smallest interval covering query, else -1

        # Sort intervals by start
        intervals.sort(key=lambda x: x[0])

        # Sort queries with original indices
        sorted_queries = sorted([(q, i) for i, q in enumerate(queries)])

        res = [-1] * len(queries)

        # MinHeap: (size, end)
        heap = []
        
        # pointer for intervals
        j = 0

        # Iterate queries in ascending order
        for q_val, q_idx in sorted_queries:

            # push all intervals starting <= query into heap
            while j < len(intervals) and intervals[j][0] <= q_val:
                start, end = intervals[j]
                size = end - start + 1
                heapq.heappush(heap, (size, end))
                j += 1

            # pop intervals ending before query
            while heap and heap[0][1] < q_val:
                heapq.heappop(heap)

            # record result
            if heap:
                res[q_idx] = heap[0][0]

        # overall: time complexity O(n log n + q log n)
        # overall: space complexity O(n)
        return res

    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        
        # Note:
        # Uses a defaultdict map for clarity.

        # Note:
        # Greedy + Min-Heap
        # 0. Direct Boundary -> empty inputs handled implicitly
        # 1. Sort intervals by start
        # 2. Iterate queries in ascending order
        # 3. Push intervals whose start <= query into min-heap (ordered by size)
        # 4. Remove intervals whose end < query
        # 5. Result -> top of heap is smallest interval covering query, else -1
        # 6. Map results back to original query order

        # Sort intervals by start
        intervals.sort(key=lambda x: x[0])

        res_map = defaultdict(int)
        # MinHeap of (size, end)
        min_heap = []
        # Pointer for intervals
        i = 0

        # Iterate queries in ascending order
        for q in sorted(queries):

            # Push all intervals starting <= query into heap
            while i < len(intervals) and intervals[i][0] <= q:
                l, r = intervals[i]
                heapq.heappush(min_heap, (r - l + 1, r))  # (size, end)
                i += 1

            # Pop intervals ending before query
            while min_heap and min_heap[0][1] < q:
                heapq.heappop(min_heap)

            # Record result
            res_map[q] = min_heap[0][0] if min_heap else -1

        # Map results back to original query order
        res = [res_map[q] for q in queries]

        # overall: time complexity O(n log n + q log n)
        # overall: space complexity O(n)
        return res

    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        
        # Note:
        # Uses a hash to avoid recomputation and pushes intervals 
        # into heap lazily.
        
        soq = sorted(queries)
        out = []
        intervals.sort(key=lambda x: x[0])
        hsh = {}
        i=0
        pq = []
        for q in soq:
            if hsh.get(q,-1) != -1:
                continue
            
            while i<len(intervals) and q>=intervals[i][0]:
                l,r = intervals[i]
                heapq.heappush(pq,(r-l+1,r))
                i+=1
            
            while pq:
                pr,end = pq[0]
                if q>end:
                    heapq.heappop(pq)
                else:
                    hsh[q]=pr
                    break

            
        
        return [hsh.get(p,-1) for p in queries]