代码随想录-算法训练营day35【贪心算法05：无重叠区间、划分字母区间、合并区间】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第八章 贪心算法 part05

● 435. 无重叠区间 
● 763.划分字母区间 
● 56. 合并区间 

 详细布置  

今天的三道题目，都算是 重叠区间 问题，大家可以好好感受一下。 都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！ 
还是属于那种，做过了也就会了，没做过就很难想出来。
不过大家把如下三题做了之后， 重叠区间 基本上差不多了

 435. 无重叠区间 

https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html  

 763.划分字母区间 

https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html  

 56. 合并区间  
本题相对来说就比较难了。

https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html  

往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任务以及具体安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任务以及具体安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR 
●day 31 任务以及具体安排：https://docs.qq.com/doc/DUG1PQ1ZZY2xXY1ly 
●day 32 任务以及具体安排：https://docs.qq.com/doc/DUGFEdGFWeVhleFF1 
●day 33 周日休息 
●day 34 任务以及具体安排：https://docs.qq.com/doc/DUEh5WFVlQkp1U0p4  
●day 35 任务以及具体安排：https://docs.qq.com/doc/DUFRWc3BGRHFXZ1pO

目录

0435_无重叠区间

0763_划分字母区间

0056_合并区间

0435_无重叠区间

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;

import java.util.Arrays;

public class _0435_无重叠区间 {
}

class Solution0435 {
    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;
    }
}

class Solution0435_2 {//按左边排序，不管右边顺序。相交的时候取最小的右边。
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        int remove = 0;
        int pre = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (pre > intervals[i][0]) {
                remove++;
                pre = Math.min(pre, intervals[i][1]);
            } else pre = intervals[i][1];
        }
        return remove;
    }
}

0763_划分字母区间

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class _0763_划分字母区间 {
}

class Solution0763 {
    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;
    }
}

class Solution0763_2 {
    /*解法二： 上述c++补充思路的Java代码实现*/
    public int[][] findPartitions(String s) {
        List<Integer> temp = new ArrayList<>();
        int[][] hash = new int[26][2];//26个字母2列 表示该字母对应的区间

        for (int i = 0; i < s.length(); i++) {
            //更新字符c对应的位置i
            char c = s.charAt(i);
            if (hash[c - 'a'][0] == 0) hash[c - 'a'][0] = i;

            hash[c - 'a'][1] = i;

            //第一个元素区别对待一下
            hash[s.charAt(0) - 'a'][0] = 0;
        }

        List<List<Integer>> h = new LinkedList<>();
        //组装区间
        for (int i = 0; i < 26; i++) {
            //if (hash[i][0] != hash[i][1]) {
            temp.clear();
            temp.add(hash[i][0]);
            temp.add(hash[i][1]);
            //System.out.println(temp);
            h.add(new ArrayList<>(temp));
            // }
        }
        // System.out.println(h);
        // System.out.println(h.size());
        int[][] res = new int[h.size()][2];
        for (int i = 0; i < h.size(); i++) {
            List<Integer> list = h.get(i);
            res[i][0] = list.get(0);
            res[i][1] = list.get(1);
        }
        return res;
    }

    public List<Integer> partitionLabels(String s) {
        int[][] partitions = findPartitions(s);
        List<Integer> res = new ArrayList<>();
        Arrays.sort(partitions, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        int right = partitions[0][1];
        int left = 0;
        for (int i = 0; i < partitions.length; i++) {
            if (partitions[i][0] > right) {
                //左边界大于右边界即可记为一次分割
                res.add(right - left + 1);
                left = partitions[i][0];
            }
            right = Math.max(right, partitions[i][1]);
        }
        //最右端
        res.add(right - left + 1);
        return res;
    }
}

0056_合并区间

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class _0056_合并区间 {
}

/**
 * 时间复杂度：O(NlogN) 排序需要 O(NlogN)
 * 空间复杂度：O(logN)  java的内置排序是快速排序，需要 O(logN) 空间
 */
class Solution0056 {
    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()][]);
    }
}

class Solution0056_2 {//版本2
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.getLast()[1]) {
                int start = res.getLast()[0];
                int end = Math.max(intervals[i][1], res.getLast()[1]);
                res.removeLast();
                res.add(new int[]{start, end});
            } else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}