#3010. /流水线

Question

说明
Gordon 的工厂需要生产 n 个产品，每个产品会在记录本上记录开始生产的时间 x 以及完成生产的时间 y。

现在 Gordon 拿到这本记录本以后想知道最多有多少件产品同时在生产线上生产。

注意：在同一时刻总是开始生产的产品先进入流水线。

输入格式
输入第一行只有一个整数 n，表示记录本上共记录了 n 件产品的信息。

接下来 n 行，每行两个整数 x 和 y，表示一件产品开始生产的时间和完成生产的时间。

输出格式
输出仅有一行，该行只有一个整数，表示最多有多少件产品同时在生产线上生产。

样例
输入数据 1
4
2 6
8 9
1 5
1 2
输出数据 1
3
提示
1 <= n <= 100000, 1 <= x <= y <= 10^8
我的空间超限怎么改？

#include<bits/stdc++.h>
using namespace std;
const int N=1e8;
int a[N],d[N],n,q,l,r,x;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        d[i]=a[i]-a[i-1];
    }for(int i=1;i<=n;i++){
        cin>>l>>r;
        d[i]+=1;
        d[i+1]-=1;
    }for(int i=1;i<=n;i++){
        a[i]=d[i]+a[i-1];
    }
    int mx=-1;
    for(int i=1;i<=n;i++){
        mx=max(mx,a[i]);
    }
    cout<<mx;
    return 0;
}

Answer 1

让【道友老李】来帮你解答，本回答参考gpt编写，并整理提供，如果还有疑问可以点击头像关注私信或评论(小黑屋了，无法评论，请私信)。

如果答案让您满意，请采纳、关注，非常感谢！

为了避免空间超限，可以尝试优化算法，不必存储所有产品的开始和结束时间，而是采用事件驱动的方式进行处理。可以使用multiset来维护当前生产线上的产品时间段，每次插入/删除一个产品的时间段时更新最多产品数量即可。 以下是修改后的代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int time;
    int is_start;
    bool operator < (const node& rhs) const {
        if(time != rhs.time){
            return time < rhs.time;
        }
        return is_start < rhs.is_start;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, ans = 0;
    cin >> n;
    vector<node> events;
    for(int i = 0; i < n; i++){
        int start, end;
        cin >> start >> end;
        events.push_back({start, 1});
        events.push_back({end, 0});
    }
    sort(events.begin(), events.end());
    multiset<int> products;
    for(auto& event : events){
        if(event.is_start){
            products.insert(event.time);
        } else {
            products.erase(products.find(event.time));
        }
        ans = max(ans, (int)products.size());
    }
    cout << ans;
    return 0;
}

这样可以避免存储大量的产品信息，空间消耗更小，提高了效率。