# Minimum number of intervals to remove so no two overlap.
# = total intervals - maximum non-overlapping set.
# Greedy: sort by end, greedily keep intervals that don't overlap.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])   # sort by END time
    count = 0
    end = float('-inf')

    for start, finish in intervals:
        if start >= end:
            end = finish    # take this interval
        else:
            count += 1      # skip (remove) overlapping interval

    return count

# eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]) → 1  (remove [1,3])

# Sort by start time. Merge current interval into last if they overlap.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])   # sort by START time
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)   # extend
        else:
            merged.append([start, end])

    return merged

# merge([[1,3],[2,6],[8,10],[15,18]]) → [[1,6],[8,10],[15,18]]

def insert(intervals, newInterval):
    result = []
    i, n = 0, len(intervals)

    # Add all intervals that end before new one starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i]); i += 1

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

    # Append the rest
    result.extend(intervals[i:])
    return result

# Minimum conference rooms = maximum concurrent meetings at any point.
# Two-pointer on sorted start and end times.

def minMeetingRooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends   = sorted(i[1] for i in intervals)

    rooms = 0
    max_rooms = 0
    j = 0   # pointer into ends

    for i in range(len(intervals)):
        rooms += 1
        if starts[i] >= ends[j]:
            rooms -= 1       # one meeting ended; reuse room
            j += 1
        max_rooms = max(max_rooms, rooms)

    return max_rooms

# minMeetingRooms([[0,30],[5,10],[15,20]]) → 2

# Greedy: track the farthest reachable index.
# If you reach a position beyond max_reach, you're stuck.

def canJump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
    return True

# Greedy BFS: at each "level" (current jump range), find the farthest
# you can reach in the next jump. Increment jumps per level.

def jump(nums):
    jumps = 0
    current_end = 0   # end of current jump range
    farthest = 0      # farthest reachable from current range

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:          # exhausted current range
            jumps += 1
            current_end = farthest    # expand to next range

    return jumps

# jump([2,3,1,1,4]) → 2

# Cooldown n between same tasks. Count max-frequency task; idle slots fill gaps.
# Result = max(actual tasks, frame formula)

from collections import Counter
import math

def leastInterval(tasks, n):
    counts = Counter(tasks)
    max_count = max(counts.values())
    max_count_tasks = sum(1 for c in counts.values() if c == max_count)

    # Slots = (max_count - 1) frames of (n+1) each + tasks tied at max
    slots = (max_count - 1) * (n + 1) + max_count_tasks
    return max(slots, len(tasks))

# leastInterval(["A","A","A","B","B","B"], 2) → 8  (A→B→idle→A→B→idle→A→B)

# Each letter must appear in only one partition.
# Greedy: extend current partition to cover the last occurrence of every
# letter seen so far. When index reaches the partition end, cut.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}   # last occurrence of each char
    result = []
    start = end = 0

    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            result.append(end - start + 1)
            start = i + 1

    return result

# partitionLabels("ababcbacadefegdehijhklij") → [9,7,8]