algorithm - 查找覆盖整组间隔的最小点数

Question

这个问题之前有人问过，Finding minimum number of points which covers entire set of intervals?现在答案是要根据结束时间对间隔进行排序。我的问题是，为什么根据开始时间排序是错误的？这是我写的代码-

   struct Interval {
   int start;
   int end;
   };
   bool helper(Interval a,Interval b)
   {
   return a.start<b.start;
   }
   int main() { 
     int t;
     cin>>t;
     while(t--)
     {
     int n,c;
     cin>>n>>c;
     vector<Interval> i(n);
     for(int j=0;j<n;j++)
     {
        cin>>i[j].start>>i[j].end;
     }

     sort(i.begin(),i.end(),helper);
     int count=1;
     Interval s=i[0];
     for(int j=1;j<n;j++)
     {
        if(i[j].start>s.end)
        {
            count++;
            s=i[j];
        }
     }
     cout<<count*c<<endl;
   }
   return 0;
}

如果我将辅助函数更改为 返回 a.end<=b.end我得到正确答案。 (我正在使用在线法官)。对我来说，按开始时间排序似乎也应该给出正确的输出，我真的想不出一个例子，它没有。谁能给我一个？

Answer 1

举个例子

按start排序时，先取红色区间。这意味着 count 不会递增，直到有一个 start 大于 10 的区间。所以你的算法的输出将为 1。但它应该是 2，因为绿色和蓝色区间不相互重叠。

OTOH，如果算法按终点(as described in the answer to the linked question)排序，那么绿色贡献点 4，蓝色贡献点 8，红色已经被覆盖。得出正确答案 2。