第八章 贪心算法 part05

•  435. 无重叠区间 

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

  思路：和上题射气球思路一样，都是要寻找重合区间，如果有重合区间就result++，并且更新右边界。

•  763.划分字母区间 

  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;
      }
  }
  

  思路：寻找一个区间内的最大距离，使得每个区间内的字母都跑不出这个区间，这就是一个结果集，用edge数组保存各个字母的最远距离，一旦i遍历到idx区间内的最远距离时，就把这个区间长度加入结果集list中。

•  56. 合并区间 

  class Solution {
      public int[][] merge(int[][] intervals) {
          Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));
          List<int[]>result = new ArrayList<>();
          int i ;
          for(i = 1 ; i < intervals.length ; i++){
              if(intervals[i-1][1] >= intervals[i][0]){
                  intervals[i][0] = intervals[i-1][0];
                  intervals[i][1] = Math.max(intervals[i-1][1], intervals[i][1]);
              }else{
                  result.add(intervals[i-1]);
              }
          }
          result.add(intervals[i-1]);
          return result.toArray(new int[result.size()][]);
      }
  }

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

  思路：与前几道题类似，都是要求重合区间，然后合并起来，注意！！要取右边界的最大值！！不要忘记比较。