func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    n, m := len(g), len(s)
    i, j := 0, 0

    for i < n && j < m {
        if s[j] >= g[i] {
            i++
        }
        j++
    }
    return i
}

func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }

    prev := nums[1] - nums[0]
    ans := 2
    if prev == 0 {
        ans = 1
    }

    for i := 2; i < n; i++ {
        diff := nums[i] - nums[i-1]
        if diff > 0 && prev <= 0 || diff < 0 && prev >= 0 {
            ans++
            prev = diff
        }
    }
    return ans
}

func maxSubArray(nums []int) int {
    n := len(nums)
    ans := math.MinInt
    sum := 0
    for i := 0; i < n; i++ {
        sum += nums[i]
        ans = max(ans, sum)
        if sum < 0 {
            sum = 0
        }
    }
    return ans
}

func maxProfit(prices []int) int {
    n := len(prices)
    ans := 0
    for i := 1; i < n; i++ {
        if prices[i] > prices[i-1] {
            ans += prices[i] - prices[i-1]
        }
    }
    return ans
}

func canJump(nums []int) bool {
    n := len(nums)
    cover := 0
    for i := 0; i <= cover; i++ {
        cover = max(i+nums[i], cover)
        if cover >= n-1 {
            return true
        }
    }
    return false
}

func jump(nums []int) int {
    n := len(nums)
    curr, next, ans := 0, 0, 0

    for i := 0; i < n-1; i++ {
        next = max(nums[i]+i, next)
        if i == curr {
            curr = next
            ans++
        }
    }
    return ans
}

func largestSumAfterKNegations(nums []int, k int) int {
    n := len(nums)
    sort.Ints(nums)

    for i := 0; i < n && nums[i] < 0 && k > 0; i, k = i+1, k-1 {
        nums[i] = -nums[i]
    }
    if k == 0 {
        return getSum(nums)
    }
    sort.Ints(nums)
    for k != 0 {
        nums[0] = -nums[0]
        k--
    }
    return getSum(nums)
}

func getSum(nums []int) int {
    ans := 0
    for _, val := range nums {
        ans += val
    }
    return ans
}

func canCompleteCircuit(gas []int, cost []int) int {
    n := len(gas)
    diff := make([]int, n)
    for i := 0; i < n; i++ {
        diff[i] = gas[i] - cost[i]
    }

    ans, i, sum, totalSum := 0, 0, 0, 0
    for ; i < n; i++ {
        sum += diff[i]
        totalSum += diff[i]
        if sum < 0 {
            sum = 0
            ans = i + 1
        }
    }

    if totalSum < 0 {
        return -1
    }
    return ans
}

func candy(ratings []int) int {
    n := len(ratings)
    need := make([]int, n)
    for i := 0; i < n; i++ {
        need[i] = 1
    }
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            need[i] = need[i-1] + 1
        }
    }
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            need[i] = max(need[i+1]+1, need[i])
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        ans += need[i]
    }
    return ans
}

func lemonadeChange(bills []int) bool {
    five, ten, twenty := 0, 0, 0
    for _, bill := range bills {
        switch bill {
        case 5:
            five++
        case 10:
            five--
            ten++
        case 20:
            if ten != 0 {
                ten--
                five -= 1
            } else {
                five -= 3
            }
            twenty++
        }
        if five < 0 || ten < 0 || twenty < 0 {
            return false
        }
    }
    return true
}

func reconstructQueue(people [][]int) [][]int {
    sort.Slice(people,func(i,j int)bool{
        if people[i][0] != people[j][0]{
            return people[i][0]>people[j][0]
        }
        return people[i][1]<people[j][1]
    })
    ans:=[][]int{}
    for _,person:=range people{
        idx:=person[1]
        ans=append(ans[:idx],append([][]int{person},ans[idx:]...)...)
    }
    return ans
}

func findMinArrowShots(points [][]int) int {
    ans:=0
    curr:=math.MinInt
    sort.Slice(points,func (i,j int)bool{
        return points[i][1]<points[j][1]
    })
    for _,point:=range points{
        if point[0]>curr{
            curr=point[1]
            ans++
        }
    }
    return ans
}

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    ans, curr := 0, math.MinInt
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    for _, interval := range intervals {
        if interval[0] >= curr {
            curr = interval[1]
            ans++
        }
    }
    return n - ans
}

func partitionLabels(s string) []int {
    m := map[rune]int{}
    for idx, c := range s {
        m[c] = idx
    }
    left, right := 0, 0
    ans := []int{}
    for idx, c := range s {
        right = max(right, m[c])
        if idx == right {
            ans = append(ans, right-left+1)
            left = right + 1
        }
    }
    return ans
}

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    ans := [][]int{}
    for _, interval := range intervals {
        if len(ans) > 0 && interval[0] <= ans[len(ans)-1][1] {
            ans[len(ans)-1][1] = max(ans[len(ans)-1][1], interval[1])
        } else {
            ans = append(ans, interval)
        }
    }
    return ans
}

func monotoneIncreasingDigits(n int) int {
    s := []byte(strconv.Itoa(n))
    i := 1
    for i < len(s) && s[i] >= s[i-1] {
        i++
    }
    if i < len(s) {
        for i > 0 && s[i] < s[i-1] {
            s[i-1]--
            i--
        }
        for i++; i < len(s); i++ {
            s[i] = '9'
        }
    }
    ans, _ := strconv.Atoi(string(s))
    return ans
}