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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

解题思路

问题核心：

• 给定气球数组 points，points[i] = [xstart, xend] 表示气球的水平直径。
• 箭在 x 处射出，可击破所有满足 xstart ≤ x ≤ xend 的气球。
• 目标：最小化箭数，使所有气球被击破。

贪心策略：

1. 排序：
   • 按气球的结束坐标 xend 升序排序（若 xend 相同，可按 xstart 排序，但不必要）。
   • 理由：优先处理结束早的气球，合并重叠区间，减少所需箭数。
2. 合并重叠区间：
   • 遍历排序后的气球，维护当前重叠区间的 [start, end]。
   • 如果新气球的 xstart > end，说明与当前区间不重叠，需新箭（sum++），更新 start = xstart, end = xend。
   • 如果重叠（xstart ≤ end），更新重叠区间：start = max(start, xstart), end = min(end, xend)。
3. 为什么贪心有效：
   • 按 xend 排序确保每次选择最早结束的气球，合并尽可能多的重叠气球，减少箭数。
   • 类似区间调度问题，最少箭数等于非重叠区间的数量。
4. 初始边界：
   • 初始化 end 为一个极小值（如 Long.MIN_VALUE），确保第一个气球触发新箭。

时间复杂度：

• 排序：O(n log n)，其中 n 是 points.length。
• 遍历：O(n)。
• 总计：O(n log n)。

空间复杂度：

• O(1)（不计排序空间）。

代码 

import java.util.*;

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        long start = Long.MIN_VALUE, end = Long.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < points.length; i++) {
            if (end < points[i][0]) {  // 不在上一个边界内
                sum++;
                start = points[i][0];
                end = points[i][1];
            } else {
                start = Math.max(start, points[i][0]);
                end = Math.min(end, points[i][1]);
            }
        }
        return sum;
    }
}

 435.无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

解题思路

问题核心：

• 给定区间数组 intervals，intervals[i] = [starti, endi] 表示一个区间。
• 目标：移除最少数量的区间，使剩余区间互不重叠（endi ≤ startj）。
• 区间端点相等（如 [1,2] 和 [2,3]）视为不重叠。

贪心策略：

1. 排序：
   • 按结束时间 endi 升序排序（若结束时间相同，可按 starti 排序，但不必要）。
   • 理由：选择结束最早的区间，最大化后续可保留的非重叠区间数，类似区间调度问题。
2. 遍历与移除：
   • 维护当前非重叠区间的结束时间 end。
   • 遍历排序后的区间：
     • 如果当前区间的 starti >= end，说明不重叠，保留该区间，更新 end = endi。
     • 否则，区间重叠，增加移除计数 count++，不更新 end（保留最早结束的区间）。
3. 为什么贪心有效：
   • 按结束时间排序确保优先选择结束早的区间，留出更多空间给后续区间。
   • 移除重叠区间时，选择保留结束最早的区间，最大化非重叠区间数。
   • 最小移除数 = 总区间数 - 最大非重叠区间数。
4. 与箭射气球的关系：
   • 本题与 LeetCode 452（Minimum Number of Arrows to Burst Balloons）等价，箭数等于最大非重叠区间数，移除数为 n - 非重叠区间数。

时间复杂度：

• 排序：O(n log n)，其中 n 是 intervals.length。
• 遍历：O(n)。
• 总计：O(n log n)。

空间复杂度：

• O(1)（不计排序空间）。

代码 

import java.util.*;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int start = Integer.MIN_VALUE, end = Integer.MIN_VALUE, count = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (end <= intervals[i][0]) {  // 不与之前边界重叠
                end = intervals[i][1];
                continue;
            } else {
                count++;
            }
        }
        return count;
    }
}

763.划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

解题思路

问题核心：

• 给定字符串 s，仅包含小写英文字母。
• 需将 s 划分为多个片段，每个字母只能出现在一个片段中。
• 目标：最大化片段数（即最小化每个片段长度），返回每个片段的长度列表。
• 划分结果连接后必须等于原字符串 s。

贪心策略：

1. 记录字母最后位置：
   • 遍历字符串 s，记录每个字母的最后出现索引（edge[c - 'a']）。
   • 这确定了每个字母必须包含在哪个片段内（从首次出现到最后出现）。
2. 动态划分片段：
   • 遍历字符串，维护当前片段的结束索引 idx（初始为 0）。
   • 对于每个位置 i，更新 idx = max(idx, edge[chars[i] - 'a'])，确保当前片段包含该字母的最后出现位置。
   • 当 i == idx 时，当前片段结束（包含所有必要字母），记录长度 i - last（last 为上个片段结束位置），更新 last = i。
3. 为什么贪心有效：
   • 每个片段尽量短（在满足字母约束下），通过选择最早可能的结束点（idx）实现。
   • 确保每个字母只出现在一个片段中（idx 覆盖字母最后出现位置）。
   • 贪心选择最大化片段数，因为每次在必须包含的范围内尽快结束片段。
4. 输出：
   • 返回长度列表，元素为每个片段的长度（i - last）。

时间复杂度：

• 记录最后位置：O(n)，n 是 s.length。
• 遍历字符串：O(n)。
• 总计：O(n)。

空间复杂度：

• edge 数组：O(26) = O(1)（固定 26 个小写字母）。
• 输出列表：O(n)（最坏情况下每个字符一个片段）。
• 总计：O(n)（主要由输出列表决定）。

代码 

import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String S) {
        // 初始化结果列表，存储每个片段的长度
        List<Integer> list = new LinkedList<>();
        
        // 记录每个字母最后出现的位置
        int[] edge = new int[26];
        char[] chars = S.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            edge[chars[i] - 'a'] = i; // 更新字母 c 的最后索引
        }
        
        // idx 表示当前片段的最远结束索引，last 表示上个片段结束位置
        int idx = 0, last = -1;
        
        // 遍历字符串，确定片段
        for (int i = 0; i < chars.length; i++) {
            // 更新当前片段的最远结束索引
            idx = Math.max(idx, edge[chars[i] - 'a']);
            
            // 如果当前位置达到片段结束索引，记录片段长度
            if (i == idx) {
                list.add(i - last); // 片段长度 = 当前索引 - 上个片段结束索引
                last = i; // 更新上个片段结束位置
            }
        }
        
        // 返回片段长度列表
        return list;
    }
}

56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

解题思路

问题核心：

• 给定区间数组 intervals，intervals[i] = [starti, endi] 表示一个区间。
• 目标：合并所有重叠区间（若 end1 >= start2，则 [start1, end1] 和 [start2, end2] 重叠），返回不重叠的区间数组。
• 输出数组需覆盖输入中的所有区间，且区间不重叠（允许端点接触，如 [1,4] 和 [4,5] 合并为 [1,5]）。

贪心策略：

1. 排序：
   • 按起始时间 starti 升序排序（若 starti 相同，可按 endi 排序，但不必要）。
   • 理由：排序后，重叠区间连续出现，便于合并。
2. 合并区间：
   • 初始化当前合并区间的 start 和 end 为第一个区间的值。
   • 遍历排序后的区间：
     • 如果当前区间的 starti > end（不重叠），将当前合并区间 [start, end] 添加到结果，更新 start = starti, end = endi。
     • 如果重叠（starti <= end），更新 end = max(end, endi)，扩展当前合并区间。
   • 遍历结束后，添加最后一个合并区间 [start, end]。
3. 为什么贪心有效：
   • 按起始时间排序确保区间按顺序处理，合并时只考虑连续的重叠区间。
   • 每次选择最大的 end 合并重叠区间，确保覆盖所有重叠部分，减少输出区间数。
   • 贪心选择最小化合并后区间数，同时保证覆盖所有输入区间。
4. 输出：
   • 使用 ArrayList 动态存储合并区间，最后转换为 int[][] 数组。

时间复杂度：

• 排序：O(n log n)，其中 n 是 intervals.length。
• 遍历合并：O(n)。
• 总计：O(n log n)。

空间复杂度：

• O(n)（ArrayList 存储结果，不计输出数组）。
• 排序可能需要 O(log n) 空间（取决于 JVM 实现）。

代码 

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        // 边界检查：空数组或 null 返回空数组
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }
        
        // 按起始时间升序排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 初始化结果列表
        List<int[]> ans = new ArrayList<>();
        
        // 初始化当前合并区间的起始和结束时间
        int start = intervals[0][0];
        int end = intervals[0][1];
        
        // 遍历区间，从第二个区间开始
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间起始时间大于上一区间结束时间，不重叠
            if (end < intervals[i][0]) {
                ans.add(new int[]{start, end}); // 添加当前合并区间
                start = intervals[i][0]; // 开始新区间
                end = intervals[i][1];
            } else {
                // 重叠，扩展当前区间的结束时间
                end = Math.max(end, intervals[i][1]);
            }
        }
        
        // 添加最后一个合并区间
        ans.add(new int[]{start, end});
        
        // 转换为 int[][] 数组
        return ans.toArray(new int[ans.size()][]);
    }
}