【贪心算法】代码随想录算法训练营第三十六天 |435.无重叠区间，763.划分字母区间，56.合并区间（待补充）

Myth丶恋晨 2024-04-23 04:20 42阅读 0赞

## 435.无重叠区间 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 \[1,2\] 和 \[2,3\] 的边界相互“接触”，但没有相互重叠。

示例 1:

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

示例 2:

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

示例 3:

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

4、视频讲解：

[贪心算法，依然是判断重叠区间 | LeetCode：435.无重叠区间\_哔哩哔哩\_bilibili][_ LeetCode_435._bilibili]

5、思路：

**相信很多同学看到这道题目都冥冥之中感觉要排序，但是究竟是按照右边界排序，还是按照左边界排序呢？**

其实都可以。主要就是为了让区间尽可能的重叠。

**我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了**。

此时问题就是要求非交叉区间的最大个数。

这里记录非交叉区间的个数还是有技巧的，如图：

![31d8d43095006a10962ca83d77df1951.png][]

区间，1，2，3，4，5，6都按照右边界排好序。

当确定区间 1 和 区间2 重叠后，如何确定是否与 区间3 也重贴呢？

就是取 区间1 和 区间2 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。

接下来就是找大于区间1结束位置的区间，是从区间4开始。**那有同学问了为什么不从区间5开始？别忘了已经是按照右边界排序的了**。

区间4结束之后，再找到区间6，所以一共记录非交叉区间的个数是三个。

总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。

/**
     首先，对传入的区间数组进行排序，按照区间的起始位置进行升序排序。
     然后，遍历排序后的区间数组，比较当前区间与前一个区间的重叠情况。
     如果当前区间与前一个区间有重叠，将当前区间的结束位置更新为前一个区间的结束位置的较小值。
     如果当前区间与前一个区间没有重叠，计数器加一。
     最后，返回原始区间数量减去计数器的值，即为删除的区间数量。
    */
    class Solution {
        public int eraseOverlapIntervals(int[][] intervals) {
            // 对传入的区间数组进行排序，按照区间的起始位置进行升序排序
            Arrays.sort(intervals, (a, b) -> {
                return Integer.compare(a[0], b[0]);
            });
            int count = 1;
            for (int i = 1; i < intervals.length; i++) {
                if (intervals[i][0] < intervals[i - 1][1]) {
                    intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
                    continue;
                } else {
                    count++;
                }
            }
            return intervals.length - count;
        }
    }

## 763.划分字母区间 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

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

提示：

*  S的长度在\[1, 500\]之间。
 *  S只包含小写字母 'a' 到 'z' 。

4、视频链接：

[贪心算法，寻找最远的出现位置！ LeetCode：763.划分字母区间\_哔哩哔哩\_bilibili][LeetCode_763._bilibili]

5、思路：

一想到分割字符串就想到了回溯，但本题其实不用回溯去暴力搜索。

题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？

如果没有接触过这种题目的话，还挺有难度的。

在遍历的过程中相当于是要找每一个字母的边界，**如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了**。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

*  统计每一个字符最后出现的位置
 *  从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

如图：

![aecafd0b9ddcdeb109d8f892adc28b02.png][]

### 总结 ###

这道题目leetcode标记为贪心算法，说实话，我没有感受到贪心，找不出局部最优推出全局最优的过程。就是用最远出现距离模拟了圈字符的行为。

但这道题目的思路是很巧妙的，所以有必要介绍给大家做一做，感受一下。

/**
     1、该函数的功能是将给定字符串分割成尽可能多的连续子串，使得每个子串的字符都不相同，并返回每个子串的长度列表。
     2、创建一个空的整数列表list，用于存储每个子串的长度。
     3、创建一个长度为26的整数数组edge，用于存储每个字符最后一次出现的索引。
     4、将输入字符串s转换为字符数组chars。
     5、遍历字符数组chars，更新edge数组，将每个字符最后一次出现的索引存储在对应位置。
     6、初始化变量idx为0，last为-1。
     7、遍历字符数组chars，更新idx为当前字符最后一次出现的索引的最大值。
     8、如果当前字符的索引等于idx，则将当前索引减去last的差值添加到list中，并更新last为当前索引。
     返回list列表。
     该函数的时间复杂度为O(n)，其中n是输入字符串的长度。
    */
    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;
            }
            int idx = 0;
            int 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.合并区间 ##

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

给出一个区间的集合，请合并所有重叠的区间。

示例 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\] 可被视为重叠区间。
 *  注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

4、视频链接：

[贪心算法，合并区间有细节！LeetCode：56.合并区间\_哔哩哔哩\_bilibili][LeetCode_56._bilibili]

5、思路：

本题的本质其实还是判断重叠区间问题。

大家如果认真做题的话，话发现和我们刚刚讲过的[452. 用最少数量的箭引爆气球(opens new window)][452. _opens new window]和 [435. 无重叠区间(opens new window)][435. _opens new window]都是一个套路。

这几道题都是判断区间重叠，区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。

所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals\[i\]\[0\] <= intervals\[i - 1\]\[1\] 即intervals\[i\]的左边界 <= intervals\[i - 1\]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）

这么说有点抽象，看图：（**注意图中区间都是按照左边界排序之后了**）

![7636ef2ec84a5e78481066fa8104833f.png][]

知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？

其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

/**
     时间复杂度 ： O(NlogN) 排序需要O(NlogN)
     空间复杂度 ： O(logN)  java 的内置排序是快速排序 需要 O(logN)空间
     1、这个函数的功能是合并给定的区间数组。具体步骤如下：
     2、将区间数组按照左边界进行排序。
     3、初始化初始起点为排序后的第一个区间的左边界，最大右边界为第一个区间的右边界。
     4、遍历排序后的区间数组，如果当前区间的左边界大于最大右边界，则将当前区间加入结果列表，并更新初始起点和最大右边界。
     5、如果当前区间的左边界小于等于最大右边界，则更新最大右边界为当前区间的右边界。
     6、遍历结束后，将最后一个区间加入结果列表。
     7、返回结果列表转换为二维数组。
     */
    class Solution {
        public int[][] merge(int[][] intervals) {
            List<int[]> res = new LinkedList<>();
            // 按照左边界排序
            Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
            // initial start 是最小左边界
            int start = intervals[0][0];
            int rightmostRightBound = intervals[0][1];
            for (int i = 1; i < intervals.length; i++) {
                // 如果左边界大于最大右边界
                if (intervals[i][0] > rightmostRightBound) {
                    // 加入区间 并且更新start
                    res.add(new int[]{start, rightmostRightBound});
                    start = intervals[i][0];
                    rightmostRightBound = intervals[i][1];
                } else {
                    // 更新最大右边界
                    rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
                }
            }
            res.add(new int[]{start, rightmostRightBound});
            return res.toArray(new int[res.size()][]);
        }
    }

[LeetCode_ -]: https://leetcode.cn/problems/non-overlapping-intervals/
[Link 1]: https://www.programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_435._bilibili]: https://www.bilibili.com/video/BV1A14y1c7E1
[31d8d43095006a10962ca83d77df1951.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/7702e5ecfe964d4a80bb6ea6bc041562.png
[LeetCode_ - 1]: https://leetcode.cn/problems/partition-labels/
[Link 2]: https://www.programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_763._bilibili]: https://www.bilibili.com/video/BV18G4y1K7d5
[aecafd0b9ddcdeb109d8f892adc28b02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/66be96cfdaba4c4592d840e58abc5d46.png
[LeetCode_ - 2]: https://leetcode.cn/problems/merge-intervals/
[Link 3]: https://www.programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_56._bilibili]: https://www.bilibili.com/video/BV1wx4y157nD
[452. _opens new window]: https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html
[435. _opens new window]: https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
[7636ef2ec84a5e78481066fa8104833f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8e416e4b134049c39e21784feb57b6bf.png