题意：

　　

题解：

　　方法①：贪心+优先级队列

　　贪心策略：按 L 从小到大排，L相同按 R 从小到大排；

　　将着 n 条线段加入到优先级队列中，优先级队列的排序规则如上；

　　定义 curX : 假象的一根线，从 0 位置扫描到 max{R} 位置；

　　通过优先级队列找出 curX 位置需要放置硬币的最优线段；

　　如何通过优先级队列实现呢？

1 #include
      
        2 using namespace std; 3 const int maxn=1e5+50; 4  5 int n; 6 struct Date 7 { 8     int l,r; 9     bool operator < (const Date &obj) const10     {11         if(l != obj.l)12             return l > obj.l;13         return r > obj.r;14     }15 }_date[maxn];16 17 int Solve()18 {19 //    Compress();20     priority_queue
       
        q;21     while(!q.empty())22         q.pop();23     for(int i=1;i <= n;++i)24         q.push(_date[i]);25 26     int ans=0;27     int curX=0;28     while(!q.empty())29     {30         Date tmp=q.top();31         q.pop();32         /**33             如果 l <= curX，那么[l,curX]是已求出最优解的的位置34             对于当前的[l,r]线段，只需要的其[curX+1,r]片段35             因为[curX+1,r]可能会对答案有贡献，所以将其加入到q中36         */37         if(tmp.l <= curX && curX+1 <= tmp.r)38             q.push(Date{curX+1,tmp.r});39         else if(tmp.l > curX)///如果l > curX，更新ans,curX40         {41             curX=tmp.l;42             ans++;43         }44     }45     return ans;46 }47 int main()48 {49 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);50     int test;51     scanf("%d",&test);52     while(test--)53     {54         scanf("%d",&n);55         for(int i=1;i <= n;++i)56             scanf("%d%d",&_date[i].l,&_date[i].r);57 58         printf("%d\n",Solve());59     }60     return 0;61 }
       
      

　　方法②：贪心+暴力

　　贪心策略：按 R 从小到大排，R 相同按 L 从小到大排；

　　从 1~n 遍历每个线段，对于第 i 条线段，暴力查找 [L,R] 最左的空位置；

1 #include
      
        2 using namespace std; 3 #define ll long long 4 #define ls(x) (x<<1) 5 #define rs(x) (x<<1|1) 6 const int maxn=1e5+50; 7  8 int n; 9 set
       
        _set;10 struct Date11 {12     int l,r;13     int len;14     bool operator < (const Date &obj) const15     {16         return r < obj.r;17     }18 }_date[maxn];19 20 int Solve()21 {22     sort(_date+1,_date+n+1);23     _set.clear();24 25     int ans=0;26     for(int i=1;i <= n;++i)27     {28         int l=_date[i].l;29         int r=_date[i].r;30         for(int j=l;j <= r;++j)31         {32             if(_set.find(j) == _set.end())///查找第i条线段可以放置硬币的最左的位置33             {34                 _set.insert(j);35                 ans++;36                 break;37             }38         }39     }40     return ans;41 }42 int main()43 {44     int test;45     scanf("%d",&test);46     while(test--)47     {48         scanf("%d",&n);49         for(int i=1;i <= n;++i)50         {51             scanf("%d%d",&_date[i].l,&_date[i].r);52             _date[i].len=_date[i].r-_date[i].l+1;53         }54         printf("%d\n",Solve());55     }56     return 0;57 }
       
      

因为，如果输入 1e5 个线段，所有线段的左右端点全部为 [1,1e9]；

那么，这个算法的时间复杂度为 O(n²logn)；

这个时间复杂度在打比赛的时候是不敢想的啊；

虽然不能说是正解，但可以借鉴一下其贪心的思路（tql）；

 

疑惑：这道题在离散化后跑一边方法①的代码wa了？？？

感觉，离散化后不影响结果啊？？