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

题目描述

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

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

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

示例

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

解题思路

进行顺序排序，设置一个区间，表示当前弓箭可以引爆的范围。如果在这个区间，则更新区间（start取较大的，end取较小的）；否则需要使用另外一支箭，并将区间更新为当前气球范围。

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> {
            if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
            return Integer.compare(a[0], b[0]);
        });
        int start = Integer.MIN_VALUE, end = Integer.MAX_VALUE;
        int ans = 1;
        for (int[] point : points) {
            if (point[0] > end) {
                ans++;
                start = point[0];
                end = point[1];
            } else {
                start = Math.max(point[0], start);
                end = Math.min(point[1], end);
            }
        }
        return ans;
    }
}

435. 无重叠区间

题目描述

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

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

示例

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

解题思路

类似上一题，对起点排序，设置终点匹配 prev，如果后续的起点小于此。则更新 prev为较小的，并增加一次移除操作。否则更新 prev为每次的终点。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        int ans = 0;
        int prev = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prev) {
                ans++;
                prev = Math.min(prev, intervals[i][1]);
            } else {
                prev = intervals[i][1];
            }
        }
        return ans;
    }
}

763. 划分字母区间

题目描述

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

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

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

示例

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

解题思路

在第一个字符和第一个字符最后一次出现的下标，之间进行遍历，如果字符的最后一次下标大于当前，则更新。直至循环结束时。

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        int start = 0;
        while (start < s.length()) {
            int end = s.lastIndexOf(s.charAt(start));
            Set<Character> set = new HashSet<>();
            for (int i = start; i < end; i++) {
                if (!set.contains(s.charAt(i))) {
                    end = Math.max(s.lastIndexOf(s.charAt(i)), end);
                    set.add(s.charAt(i));
                }
            }
            ans.add(end - start + 1);
            start = end + 1;
        }
        return ans;
    }
}