藍橋杯訓練——[藍橋杯][算法提高VIP]線段和點(貪心)

題目連結：https://www.dotcpp.com/oj/contest2388_problem1.html

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
struct node
{
	ll l,r;
}a[10010];
bool cmp(node x,node y){
	if(x.l==y.l){
		return x.r<y.r;
	}
	return x.l<y.l;
}
ll d[10010];//坐标點
ll sum[50010];//sum[number]，表示小于等于number的坐标點的個數
int main()
{
	IOS;
	ll n,m,x;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>d[i];
		//d[i]++;
	}
	ll maxn=0;
	for(int i=1;i<=m;i++){
		cin>>a[i].l>>a[i].r;
		//a[i].l++;a[i].r++;
		maxn=max(maxn,a[i].r);//更新最右邊界值
	}
	//排序
	sort(a+1,a+1+m,cmp);
	sort(d+1,d+1+n);
	//------求sum數組(字首和)--------------
	ll pre=0;
	sum[0]=0;
	for(int i=1;i<=n;i++){
		while(++pre<d[i]){
			sum[pre]=sum[pre-1];
		}
		sum[pre]=sum[pre-1]+1;
	}
	while(++pre<=maxn){
		sum[pre]=sum[pre-1];
	}
	//------sum數組完成-------------------
	//-----貪心求最少的點------------------
	ll ans=0,right,i;
	for(i=1;i<=m;){
		//區間[a[i].l,a[i].r]的坐标沒有直接break；
		if(sum[a[i].r]-sum[a[i].l-1]<=0)break;
		ans++;//加入一個最優點
		right=a[i].r;//該點的最右邊界
		//----檢查該點最多能滿足接下來的幾個區間------------
		for(i++;i<=m;i++){
			if(a[i].l>right)break;//下一個區間和目前的最優點所在區間沒有交集
			if(a[i].r<right)right=a[i].r;//取最小的右邊界
			if(sum[right]-sum[a[i].l-1]<=0)break;//不能滿足了
		}
	}
	//------最優解完成----------------------
	if(i<=m)cout<<-1<<endl;//無解
	else cout<<ans<<endl;
	getchar();
	getchar();
	return 0;
}