首页 > 代码库 > hiho 第155周 任务分配

hiho 第155周 任务分配

技术分享

最小路径覆盖会超时;

贪心思路:

按照开始时间排序,然后根据结束时间,维护一个以结束时间的单调递增的队列,每次与最快结束的任务进行比较即可;

技术分享
/*#include <cstdio>#include <algorithm>#include <cmath>#include <vector>#include <cstring>using namespace std;const int maxn = 100000+5;struct BPM {    int n,m;    vector<int> G[maxn];    int left[maxn];    bool T[maxn];    int right[maxn];    bool S[maxn];    void init(int n,int m) {        this->n = n;        this->m = m;        for(int i=0;i<n;i++)            G[i].clear();    }    void AddEdge(int u,int v) {        G[u].push_back(v);    }    bool match(int u) {        S[u] = true;        for(int i=0;i<G[u].size();i++) {            int v = G[u][i];            if(!T[v]) {                T[v] = true;                if(left[v]==-1||match(left[v])) {                    left[v] = u;                    right[u] = v;                    return true;                }            }        }        return false;    }    int solve() {        memset(left,-1,sizeof(left));        memset(right,-1,sizeof(right));        int ans = 0;        for(int u=0;u<n;u++) {            memset(S,0,sizeof(S));            memset(T,0,sizeof(T));            if(match(u))                ans++;        }        return ans;    }}sol;struct Node {    int s,e;}node[maxn];int main(){    int n;    scanf("%d",&n);    sol.init(n,n);    for(int i=0;i<n;i++)        scanf("%d%d",&node[i].s,&node[i].e);    for(int i=0;i<n;i++)        for(int j=i+1;j<n;j++)            if(node[i].e<=node[j].s)                sol.AddEdge(i,j);            else if(node[i].s>=node[j].e)                sol.AddEdge(j,i);    printf("%d\n",n-sol.solve());    return 0;}*/#include <bits/stdc++.h>using namespace std;const int maxn = 100000+5;struct Node {    int s,e;    bool operator < (const Node & rhs) const {        return s < rhs.s;    }}node[maxn];int main(){    int n;    scanf("%d",&n);    for(int i=0;i<n;i++)        scanf("%d%d",&node[i].s,&node[i].e);    sort(node,node+n);    priority_queue<int,vector<int>,greater<int> > Q;    Q.push(node[0].e);    for(int i=1;i<n;i++) {        if(Q.top()<=node[i].s)        {            Q.pop();            Q.push(node[i].e);        }        else Q.push(node[i].e);    }    printf("%d\n",Q.size());    return 0;}
View Code

 

hiho 第155周 任务分配