计蒜客 区间包含(活动安排问题)

已知 n 个左闭右开区间 [ a , b) ，对其进行 m 次询问，求区间 [ l , r ] 最多可以包含 n 个区间中的多少个区间，并且被包含的所有区间都不相交。

输入格式

输入包含多组测试数据，对于每组测试数据：

第一行包含两个整数 n m ( 1 ≤ n , m ≤ 100000 ) 。

接下来 n 行每行包含两个整数 a b ( 0 ≤ a < b ≤ 10^910​9​​ ) 。

接下来 m 行每行包含两个整数 l r ( 0 ≤ l < r ≤ 10^910​9​​ ) 。

输出格式

对于每组测试数据，输出 m 行，每行包含一个整数。

样例输入

4 3
1 3
2 4
1 4
1 2
1 2
1 3
1 4

样例输出

1
1
2

代码:

#include <iostream>
#include <algorithm>
using namespace std;
 int m,n;
struct node {
    int s,e;
}a[100010],b[100010];   
int cmp(node a,node b) {    //对区间进行排序，按输入活动的非减序进行排列
    if(a.e==b.e)
        return a.s<b.s;
    return a.e<b.e;
}
int fun1(node s) {          //用二分搜索的方式查找需要求的活动的r在活动中的位置，减少查找次序
    int num1=0, num2=0;
    int left=1;
    int right=m;
    int mid;
    while(left<right) {
        mid=(left+right)/2;
        if(a[mid].e==s.e)
            return mid;
        else if(a[mid].e>s.e)
            right=mid-1;
        else
            left=mid+1;
    }
    return mid;
    
}
int main() {
    while(cin>>m>>n) {
    for(int i=1;i<=m;i++)
        cin>>a[i].s>>a[i].e;
    sort(a+1,a+1+m,cmp);
    /*for(int i=1;i<=m;i++)
        cout<<a[i].s<<" "<<a[i].e<<endl;*/
        for(int j=1;j<=n;j++)
        {
            int num=0;
            cin>>b[j].s>>b[j].e;
            int t=fun1(b[j]);
            for(int i=1;i<=t+1;i++)    //为了保险，所以取t+1
                if(a[i].s>=b[j].s&&a[i].e<=b[j].e) {
                    num++;
                    b[j].s=a[i].e;
                }
            cout<<num<<endl;
        }
    }
    return 0;
}

//在没有fun1函数的时候，程序的时间复杂度为O(mn)，在数据非常大时，会有超时的危险(的确超时了，大家可以试一下)，其他的基本没什么问题了，很久之前在写题的时候，看了一下网上的，完全不怎么懂，所以后来自己又试着写了一下。