蒟蒻求助（ orz ）

题目描述

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。只有当c<=a 且 b<=d 时，我们才认为区间[a,b]被区间[c,d]覆盖。在完成所有删除操作后，请你返回列表中剩余区间的数目。

输入格式

第一行输入一个整数n，代表有n个区间。以下n行，每行输入两个整数L，R，L代表区间左边界，R代表区间右边界。

输出格式

输出一个整数，代表列表中剩余区间的数目。

样例

Input 1

1 4

3 6

2 8

Output 1

样例解释

第一个区间[1,4]不能被其他区域覆盖，第三个区间[3,6]被[2,8]覆盖

数据范围

1<=n<=1000; 0<=l,r<=1e5; 不会存在相同的区间。

本蒟蒻代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
  int n; cin>>n;
  vector<pair<int ,int> > pr(n+1);
  for(int i=1;i<=n;i++) 
    cin>>pr[i].first>>pr[i].second;
  sort(pr.begin()+1,pr.end(),[&](pair<int,int> a,pair<int,int> b){
    if(a.first!=b.first) return a.first<b.first;
    return a.second>b.second;
  });
  int last=-1,res=0;
  for(int i=1;i<=n;i++){
    if(pr[i].second<=last) res++;
    last+max(last,pr[i].second);
  }
  cout<<n-res;
  return 0;
}

求调，谢谢

蒟蒻求助（ orz ）

讨论操作

题目描述

输入格式

输出格式

样例

样例解释

数据范围

回复

相关推荐

蒟蒻求助（ orz ）