题解 | #货物种类#

题解： 该题使用贪心的解题思路吧货物序号从小到大排序通过a,b数组来计算结果

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct node
{
    int l,r,date;
    bool operator <(const node &W) const
    {
        return date<W.date;//结构体贪心；
    }
}e[N];
int a[N],b[N];//a存放的是当前地方货物的序号，B存放的是当前地方的货物个数。

int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].date);
    }
    sort(e,e+m);//结构体从小到大排序；
    for(int i=0;i<m;i++)
    {
        int l=e[i].l,r=e[i].r,d=e[i].date；
       for(int j=l;j<=r;j++)
       {
           if(a[j]<d) {a[j]=d;
           //如果该货物序号大于当前地方的货物序号，则当前货物个数++；
               b[j]++;
                      }
       }
    }
    int res=-1,ans=0;
   
    for(int i=1;i<=n;i++)
    { 
        if(b[i]>res) {//寻找最大的货物个数；
            res=b[i];
            ans=i;
    }
    }
    printf("%d\n",ans);
    
    return 0;
}

不知道为什么这里不会超时 时间复杂度最大为O(nm)