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

        return n+1

    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        
        # Note:
        # Iterate over all intervals:
        #   1. Interval ends before newInterval starts -> add to list
        #   2. Interval overlaps -> merge into newInterval, then add
        #   3. Interval starts after newInterval ends -> add to list
        # Result -> merged list of intervals

        n = len(intervals)

        res = []

        # to create merged interval
        start = newInterval[0]
        end = newInterval[1]

        i = 0

        # 1. Interval ends before newInterval starts -> add to list
        while i < n and intervals[i][1] < start:
            res.append(intervals[i])
            i += 1

        # 2. Interval overlaps -> merge into newInterval, then add
        while i < n and intervals[i][0] <= end:

            # update start and end of merged interval
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1

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

        # 3. Interval starts after newInterval ends -> add to list
        while i < n:
            res.append(intervals[i])
            i += 1

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

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # Greedy / Sorting approach
        # 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, merge; else, append
        # 4. Result -> list of merged, non-overlapping intervals

        # Empty check
        if not intervals:
            return []

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

        # Initialize with first interval
        merged = [intervals[0]]

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

            # curr interval
            current = intervals[i]

            # rightmost interval
            last_merged = merged[-1]

            # if intervals overlap, merge
            if current[0] <= last_merged[1]:
                last_merged[1] = max(last_merged[1], current[1])

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

        # overall: time complexity O(n log n)
        # overall: space complexity O(n)
        return merged 

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # Greedy / Heap approach
        # 1. Push all intervals into a min-heap (ordered by start)
        # 2. Pop intervals one by one
        # 3. Interval does not overlap with end of array, append
        # 4. Interval overlaps with end of array, merge 
        # Result -> List of merged intervals

        # Empty check
        if not intervals:
            return []

        # 1. Push all intervals into a min-heap (ordered by start)
        heap = [(s, e) for s, e in intervals]
        heapq.heapify(heap)

        merged = []

        # 2. Pop intervals one by one
        while heap:
            start, end = heapq.heappop(heap)

            # 3. Interval does not overlap with end of array, append
            if not merged or merged[-1][1] < start:
                merged.append([start, end])

            # 4. Interval overlaps with end of array, merge 
            else:
                merged[-1][1] = max(merged[-1][1], end)

        # overall: time complexity O(n log n) (heapify + n pops)
        # overall: space complexity O(n) for merged list
        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]