代码随想录算法训练营第三十天 | 452、435、763

452. 用最少数量的箭引爆气球

package main

import (
    "math"
    "sort"
)

func findMinArrowShots(points [][]int) int {
    if len(points) == 0 {
        return 0
    }
    // 按结束坐标升序排序
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })

    arrows := 0
    arrowPos := math.MinInt64 // 初始箭头位置设为极小值

    for _, p := range points {
        if p[0] > arrowPos { // 当前区间无法被之前的箭覆盖
            arrows++
            arrowPos = p[1] // 在区间末尾射箭以覆盖尽可能多的后续区间
        }
    }
    return arrows
}

435. 无重叠区间

package main

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    if n == 0 {
        return 0
    }
    // 按区间结束时间升序排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    count := 1 // 至少可以保留一个区间
    end := intervals[0][1]

    for i := 1; i < n; i++ {
        if intervals[i][0] >= end {
            count++
            end = intervals[i][1]
        }
    }
    return n - count // 总区间数 - 最大保留数 = 需移除数
}

763. 划分字母区间

package main

func partitionLabels(s string) []int {
    lastPos := [26]int{} // 存储每个字符最后出现的位置
    for i, c := range s {
        lastPos[c-'a'] = i
    }

    start, end := 0, 0
    result := make([]int, 0)

    for i, c := range s {
        // 不断扩展当前分区的结束位置
        if lastPos[c-'a'] > end {
            end = lastPos[c-'a']
        }

        // 到达当前分区的结束位置时记录长度
        if i == end {
            result = append(result, end-start+1)
            start = end + 1 // 重置起始位置为下一分区的起点
        }
    }

    return result
}