客户订单的最短平均等待时间

Question

https://www.hackerrank.com/challenges/minimum-average-waiting-time/problem这是一个hackerrank问题的链接。我正在努力。它通过了一些测试用例，失败了一些。我在STL中使用了内置的优先级队列模板。代码如下，

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct customer
{
    long long arrTime;
    long long cookTime;
    long long index;
};
void swap(customer& a,customer& b)
{
    customer &temp=a;
    a=b;
    b=temp;
}
bool compare( customer& a, customer& b)
{
    return a.arrTime<b.arrTime;
}
struct Compare1
{
    bool operator()(customer a,customer b)
    {
        return a.cookTime>b.cookTime;
    }
};
struct Compare2
{
    bool operator()(customer a,customer b)
    {
        return a.arrTime>b.arrTime;
    }
};
int main()
{
    vector<customer>c;
    vector<bool>done;
    long long n;
    cin>>n;
    for(long long i=0;i<n;i++)
    {
        customer cust;
        cin>>cust.arrTime;
        cin>>cust.cookTime;
        cust.index=i;
        c.push_back(cust);
        done.push_back(false);
    }
    sort(c.begin(),c.end(),compare);
    for(long long i=0;i<n-1;i++)
    {
        if(c[i].arrTime==c[i+1].arrTime && c[i].cookTime>c[i].cookTime)
        {
            swap(c[i],c[i+1]);
        }
    }
    priority_queue<customer,vector<customer>,Compare1> waitList;
    vector<long long>tat(n);
    vector<long long>ct(n);

    //next step- priority queue work starts
    long long count=0;
    long long totalTime=0;

    long long i=0;
    while(count!=n)
    {
        while(i<n && c[i].arrTime<=totalTime)
        {
            waitList.push(c[i]);
            i++;
        }
        customer next;
        if(!waitList.empty())
        {
            next=waitList.top();
            //cout<<"Job "<<next.index<<endl;
            waitList.pop();
            totalTime+=next.cookTime;
            ct[next.index]=totalTime;
            done[next.index]=true;  
            count++;

        }
        else if(i<n)
        {
            next=c[i];
            //cout<<"Job "<<next.index<<endl;
            i++;
            totalTime+=next.cookTime;
            ct[next.index]=totalTime;
            done[next.index]=true;  
            count++;
        }

    }
    long long sum=0;
    for(long long i=0;i<n;i++)
    {
        tat[i]=ct[i]-c[i].arrTime;
        sum+=tat[i];
    }
    cout<<sum/n;
    return 0;
}

我针对这个问题查找了一个叫做非抢占式优先调度的算法并实现了它。我的疑问：这个调度算法是解决问题的正确算法吗？我想知道我在实现调度算法时是否有任何错误。或者任何其他算法来实现它。这里是变量名称的描述，

tat数组代表工作的总周转时间

ct阵列代表完成时间。

我考虑过周转时间=非抢占式优先级调度的等待时间。

完成只是一个标志数组，用于指示标记为完成的进程。

arrTime 代表 到达时间。

CookTime代表烹饪时间（而不是实际算法中进程的爆发时间）

Answer 1

首先，对问题的重要方面进行简短解释。

< li >订单的顺序可能不正确，这意味着它们可能没有按到达时间排序。所以，一定要先按到达时间排序。 < li >重要的是要认识到，厨师必须从等待的订单中选择烹饪时间最短的订单。这样，最终的等待时间总是最短的。 < li >此外，如果厨师没有要处理的订单,“当前”时间可以播放到下一个到达的订单。

除了接受的答案之外，C解决方案（因为问题用C标签标记）可能如下所示。

#include <bits/stdc++.h>

using namespace std;

struct customer {
    uint64_t arrivalTime;
    uint64_t cookingTime;    
};

/*
 * Complete the minimumAverage function below.
 */
uint64_t minimumAverage(std::deque<customer> clients, uint32_t numberOfClients) {
    auto compareByArrivalTime = [](customer const &client1, customer const &client2)
            {
                return client1.arrivalTime < client2.arrivalTime;
            };
    
    auto compareByCookingTime = [](const customer &client1, const customer &client2)
            {
                return client1.cookingTime > client2.cookingTime;
            };
    
    std::sort(clients.begin(), clients.end(), compareByArrivalTime);
    
    std::priority_queue<customer, std::vector<customer>, decltype(compareByCookingTime)> clientPriorityQueue(compareByCookingTime);
    
    uint64_t minWaitingTime = 0;
    uint64_t currentTime = clients.front().arrivalTime;
    for (auto servedClient = 1; servedClient <= numberOfClients; servedClient++) {
        while (!clients.empty() && currentTime >= clients.front().arrivalTime) {
            clientPriorityQueue.push(clients.front());
            clients.pop_front();
        } 
        
        customer bestClient = clientPriorityQueue.top();
        clientPriorityQueue.pop();
        
        uint64_t arrivalTime = bestClient.arrivalTime;
        uint64_t cookingTime = bestClient.cookingTime;
        minWaitingTime += (currentTime - arrivalTime + cookingTime);
        currentTime += cookingTime;
        
        if (!clients.empty()) {
            currentTime = std::max(currentTime, clients.front().arrivalTime);    
        }
    }
    
    return minWaitingTime / numberOfClients;
}

int main()
{
    uint32_t n;
    std::cin >> n;

    std::deque<customer> clients;
    for (auto i = 0; i < n; i++) {
        customer client;
        std::cin >> client.arrivalTime >> client.cookingTime;
        clients.push_back(client);
    }

    uint64_t result = minimumAverage(clients, n);

    std::cout << result << "\n";

    return 0;
}

Answer 2

我想你错过了这样的情况，即有多个工作同时开始，所有这些工作都可以在下一个工作开始之前完成，这是非常小的。

例如

5
0 3
0 2
0 4
10 2
10 1

应该先查询前3个项目，并在查询其他2个项目之前处理完所有项目。这个案子在你的案子里会失败。

其他意见:

不需要用于在烹饪时间中排列向量的 for 循环，并且编码错误。

for(long long i=0;i<n-1;i++)
{
    if(c[i].arrTime==c[i+1].arrTime && c[i].cookTime>c[i].cookTime)
    {
        swap(c[i],c[i+1]);
    }
}

必须是' c[i]。烹饪时间

下面给出了一个传递所有用python编写的案例的工作解决方案以供参考。

import heapq

def getAvgWaitTime(n, cust):
    heap = []
    curTime = 0
    waitTime = 0
    cust = sorted(cust)
    i = 0

    while i < n:
        if curTime < cust[i][0]:
            curTime = cust[i][0]
        while i < n and (curTime >= cust[i][0]):
            heapq.heappush(heap, (cust[i][1], cust[i][0]))
            i += 1

        while (i < n) and curTime < cust[i][0] and len(heap) > 0:
            time, wait = calculateWaiting(heap, curTime)
            curTime += time
            waitTime += wait

    # Clear all the jobs
    while len(heap) > 0:
        time, wait = calculateWaiting(heap, curTime)
        curTime += time
        waitTime += wait

    return waitTime / n


def calculateWaiting(heap, curTime):
    wait = 0
    cur = heapq.heappop(heap)
    wait = curTime - cur[1] + cur[0] 
    return (cur[0], wait)


n = int(raw_input().strip())
cust = []
for i in range(n):
    ar = map(int, raw_input().strip().split(' '))
    cust.append((ar[0], ar[1]))


result = getAvgWaitTime(n, cust)
print result

希望对您有所帮助！