解法一：贪心

贪心算法的经典问题——活动安排。按照结束值升序排列。首先第一项必选，然后从第二项开始，后续的区间如果只要与上一个已选区间不重叠就选。按照此贪心策略，可以求出最多可选的不重叠区间的数量，即可反推出最少需要删除区间的数量。

  1. import java.util.Arrays;
  3. class Solution {
  4.     public int eraseOverlapIntervals(int[][] intervals) {
  5.         if (intervals.length == 0) {
  6.             return 0;
  7.         }
  8.         Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
  9.         int ans = 1;
  10.         int lastFinal = intervals[0][1];
  11.         for (int i = 1; i < intervals.length; ++i) {
  12.             if (intervals[i][0] >= lastFinal) {
  13.                 lastFinal = intervals[i][1];
  14.                 ++ans;
  15.             }
  16.         }
  17.         return intervals.length - ans;
  18.     }
  19. }