CSES - Movie Festival | Lễ hội phim
Xem PDF
Điểm:
1100 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Trong một lễ hội phim, \(n\) bộ phim sẽ được chiếu. Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim. Số lượng phim tối đa bạn có thể xem trọn vẹn là bao nhiêu?
Input
- Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng bộ phim.
- Sau này, có \(n\) dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian bắt đầu và kết thúc của một bộ phim.
Output
- In một số nguyên: số lượng phim tối đa.
Constraints
- \(1 \leq n \leq 2 \cdot 10^5\)
- \(1 \leq a < b \leq 10^9\)
Example
Sample input
3
3 5
4 9
5 8
Sample output
2
Bình luận
Hint: sort + cnp (Vì a[i] <= 1e9)
include <bits/stdc++.h>
using namespace std;
bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
return a.second<b.second;
}
pair<long long,long long> a[300005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].first>>a[i].second;
}
sort(a+1,a+n+1,cmp);
int dem=0,x=0;
for(int i=1;i<=n;i++)
{
if(a[i].first>=x)
{
dem++;
x=a[i].second;
}
}
cout<<dem;
}
Admin cho mình xin hint với :>