LeetCode刷题之贪心算法—重叠区间

Leetcode之 重叠区间 （最少数量箭引爆气球）

1.重叠区间：一组二维数组，它的0列是开始，1列是结束。最少要删除多少个子数组，各子区间才不重叠

 方法一：直接记录交叉区间个数
 static bool cmp(vector& a, vector& b)
     {
         return a[1]     }
     int eraseOverlapIntervals(vector>& intervals) {
         if(intervals.size()==0) return 0;
         sort(intervals.begin(),intervals.end(),cmp);
         int res=0;//交叉数
         for(int i=1; i         {
             if(intervals[i][0]             {
                 res++;
                 intervals[i][1]=intervals[i-1][1];
             }
         }
         return res++;

 方法二：先找出交叉区间
 static bool cmp(vector& a, vector& b)
     {
         return a[1]     }
     int eraseOverlapIntervals(vector>& intervals) {
         if(intervals.size()==0) return 0;
         sort(intervals.begin(),intervals.end(),cmp);
         int res=1;//未交叉数
         int start intervals[0][1];
         for(vectorinterval:intervals)
         {
             if(start<=interval[0])
             {
                 res++;
                 start=piont[1];
             }
         }
         return intervals.size() - res;
         

2.引爆气球 ：寻找交叉区间，不过边界点重叠也算！！

 ?
 static bool cmp(vector& a, vector& b)
     {
         return a[1]     }
     int eraseOverlapIntervals(vector>& intervals) {
         if(intervals.size()==0) return 0;
         sort(intervals.begin(),intervals.end(),cmp);
         int res=1;//未交叉数
         int start intervals[0][1];
         for(vectorinterval:intervals)
         {
             if(start             {
                 res++;
                 start=interval[1];
             }
         }
         return res;  //注意返回值
         

TRANSLATE with

Bing Webmaster Portal