Click here to Skip to main content
15,881,173 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Airport is divided to many Runways. Each runway has a mixed fixed delay amount of
time to keep a plane on runway. If airplane delay time > runway delay time than airplane
needs to take out from a runway, then it is considered as missed and starts from again
from a runway. You need to find out the minimum total delay for particular input. First
input line is number of runways. Second input line is delay of each runway.
Third input line is capacity of each runway to accommodate planes. Forth input line is
total number of planes. Fifth input line is maximum delay an airplane can afford. If it
exceed the runway delay time it is miss and it needs to start from again from a runway.
You need to show how you managed the runways as output as well.
Examples:(All are from user input)
5
2 2 3 5 7
2 2 2 2 2
8
1 1 1 1 2 2 3 3
Answer= 3

calculetion:(For another Example)
      2 2 3 5 7   (runways delay times)
     ____________
      1 1 1 5 3  (Air planes Delay times are less or equal
      1 2 2 0 0  than runways delay)
      __________
1sec -0 0 0 4 2
1sec -0 1 1 3 1
1sec -0 0 0 2 0
1sec -0 0 0 1 0
1sec -0 0 0 0 0 
________________
Dealay Time=(1+1+1+1+1)sec
           =5 second
Answer=5


What I have tried:

For All other inputs Answer is showing 0;
C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int numOfRun,numOfPl,minDl=0;
    int DR[10000],CP[10000],DP[10000],A[10000];
    cin>>numOfRun;
    for(int i=0;i<numOfRun;i++)
    {
        cin>>DR[i];
    }
    for(int i=0;i<numOfRun;i++)
    {
        cin>>CP[i];
    }
    cin>>numOfPl;
    for(int i=0;i<numOfPl;i++)
    {
        cin>>DP[i];
    }
    for(int i=0,j=0,k=0;i<numOfPl;k++,j++)
    {
        if(j>=numOfRun)
        {
            j=0;
        }
        if(DP[i]<=DR[j]&&CP[j]>0)
        {
            CP[i]--;
            A[k]=DP[i];
            i++;
        }
        else
        {
            minDl+=DP[i];
        }
    }
    cout<<"Answer = "<<minDl<<endl;
    for(int i=0,k=0;k<numOfPl;)
    {
        for(int j=0;j<numOfRun;j++,i++)
        {
            if(A[i]<=0)
                cout<<"  ";
            else
            {
             cout<<A[i]<<" ";
             k++;
            }
        }
        cout<<endl;
    }

    return 0;
}

/*
5
2 2 3 5 7
2 2 2 2 2
8
1 1 1 1 2 2 3 3
*/


This is another one I have tried..but the answers are not currect..
C++
#include<iostream>

using namespace std;

// Node class
class Node{
    public:
        float value;
        Node *next;
};

// Queue class
class Queue{
    public:
        // Pointer to keep track of the first value
        Node *first=NULL;

    // This function appends an integer at the end of the queue
    void enqueue(float d){
        Node *n = new Node();
        n->value = d;
        n->next = NULL;
        if(first == NULL){
            first = n;
        }else{
            Node *p = first;
            while(p->next != NULL){
                p=p->next;
            }
            p->next = n;
        }
    }

    // This function removes and returns the first value in the queue
    float dequeue(){
        if(first == NULL){
            //cout << "Queue is empty!" << endl;
            return -1;
        }
        Node *p = first;
        first = first->next;
        float v=p->value;
        delete p;
        return v;
    }

    int getSize(){
        if(first == NULL){
            return 0;
        }else{
            Node *p = first;
            int count=0;
            while(p != NULL){
                p=p->next;
                count++;
            }
            return count;
        }
    }

    int getSum(){
        int sum=0;
        if(first!=NULL){
            Node *p = first;
            while(p!=NULL){
                sum+=p->value;
                p=p->next;
            }
        }
        return sum;
    }
};

int getMax(int A[], int n){
    int max=A[0];
    for(int i=0;i<n;i++){
        if(max<A[i])
            max=A[i];
    }
    return max;
}

int getMaxTotalDelay(Queue Q[], int n, int planeDelay, int runwayIndex){
    int max=0;
    int sum;
    for(int i=0;i<n;i++){
        if(runwayIndex==i){
            sum=Q[i].getSum()+planeDelay;
        }
        else{
            sum=Q[i].getSum();
        }
        if(max<sum)
            max=sum;
    }
    return max;
}

int main(){
    int runway,plane;
    runway=5;
    plane=10;
    int runwaydelay[]    = {2,2,3,5,7};
    int runwayCapacity[] = {2,2,2,2,2};
    int planedelay[]     = {1,1,1,3,3,1,2,2,2,2};
    int nQc=0;
    Queue pDelay;
    for(int i=plane-1;i>=0;i--){
        pDelay.enqueue(planedelay[i]);
    }
    Queue Q[runway];
    int maxRunwayCapacity = getMax(runwayCapacity,runway);

    while(pDelay.getSize()>0){
        int minDelay = 99999;
        int minTotalDelay = 99999;
        int minTotalDelayIndex = 99999;
        int minDelayIndex = -1;
        int delay = pDelay.dequeue();
        for(int i=0; i<runway; i++){
            minTotalDelay=99999;
            for(int j=0;j<runway;j++){
                if(runwayCapacity[j]>Q[j].getSize() && runwaydelay[j]-delay>=0){
                    int mtd = getMaxTotalDelay(Q,runway,delay,j);
                    if(minTotalDelay>mtd){
                        minTotalDelay=mtd;
                        minTotalDelayIndex=j;
                    }
                }
            }
            if(runwaydelay[i]-delay>=0 && minDelay>runwaydelay[i]-delay && runwayCapacity[i]>Q[i].getSize()){
                minDelay = runwaydelay[i]-delay;
                minDelayIndex = i;
            }
        }
        if(minDelayIndex==-1){
            cout<<"Impossible"<<endl;
        }else{
            if(getMaxTotalDelay(Q,runway,delay,minDelayIndex)<getMaxTotalDelay(Q,runway,delay,minTotalDelayIndex)){
                cout<<"Plane delay: "<<delay<<" | Runway delay: "<<runwaydelay[minDelayIndex]<<" | Runway index: "<<minDelayIndex<<endl;
                Q[minDelayIndex].enqueue(delay);
            }else{
                cout<<"Plane delay: "<<delay<<" | Runway delay: "<<runwaydelay[minTotalDelayIndex]<<" | Runway index: "<<minTotalDelayIndex<<endl;
                Q[minTotalDelayIndex].enqueue(delay);
            }
        }
    }
    cout<<endl;
    for(int i=0;i<runway;i++){
        cout<<runwaydelay[i]<<",";
    }
    cout<<endl;
    for(int i=0;i<runway;i++){
        cout<<runwayCapacity[i]<<",";
    }
    cout<<endl;
    for(int i=0;i<plane;i++){
        cout<<planedelay[i]<<",";
    }
    cout<<endl;
    int minTotalDelay = getMaxTotalDelay(Q,runway,0,0);
    int r = runway;
    int c = getMax(runwayCapacity,runway);
    int outputArray[r][c];
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            outputArray[i][j]=-1;
        }
    }
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            int temp = Q[i].dequeue();
            if(temp > 0)
                outputArray[i][j]=temp;
        }
    }
    cout<<endl;
    for(int i=0;i<c;i++){
        for(int j=0;j<r;j++){
            if(outputArray[j][i]>0)
                cout<<outputArray[j][i]<<" ";
            else
                cout<<"  ";
        }
        cout<<endl;
    }
    cout<<"Minimum total delay: "<<minTotalDelay<<endl;
Posted
Updated 12-Jul-19 2:52am
v4
Comments
Stefan_Lang 12-Jul-19 11:40am    
Please make sure the description of the task is accurate. Your choice of words is confusing, and possibly misleading. For example "Delay" means that something is happening later than it is supposed to be - but apparently that this is not at all what you're trying to describe!

Moreover, it might help to explain the context more accurately, even if it isn't needed to solve the task - it could help figuring out what you really mean. For example, it's not clear whether the planes are leaving or arriving.

Also, this task is about time passing, and reducing that time. But a lot of time-related information is missing, such as when, exactly, each plane is supposed to start or arrive.

Besides, the concept of runway maximum delay time and runway capacity seems very odd. I see no reason why there should be a limit in time or number of planes that a runway can handle. Either it's occupied or not. Whatever is the reason for these limitations, you should better make sure that the effect of the limitations is explained clearly - because there is a high likelyhood that we don't understand what is required.

We can't tell - we can't run your code under the same conditions you do, and that's essential for working out what is happening.

So, it's going to be up to you.
Fortunately, you have a tool available to you which will help you find out what is going on: the debugger. If you don't know how to use it then a quick Google for the name of your IDE and "debugger" should give you the info you need.

Put a breakpoint on the first line in the function, and run your code through the debugger. Then look at your code, and at your data and work out what should happen manually. Then single step each line checking that what you expected to happen is exactly what did. When it isn't, that's when you have a problem, and you can back-track (or run it again and look more closely) to find out why.

Sorry, but we can't do that for you - time for you to learn a new (and very, very useful) skill: debugging!

And do yourself a favour: stop naming your variables so they are quick to type. Usernames that describe what they are used for and your code becomes a lot easier to read, which makes they easier to fix, and maintain. This saves you a heck of a lot more time than you would ever save by typing less.
 
Share this answer
 
v2
Comments
nirvikprantor 11-Jul-19 15:42pm    
Can you solve this problem by your self?
OriginalGriff 11-Jul-19 15:49pm    
With your code, your data, your inputs, and your debugger - yes.
Without them? No.

But then, I wouldn't write code like that because I'm not a student any more ...

Trust me, this homework assignment isn't complicated: grab your debugger and start finding exactly what your code is doing. Learn to use it, and your future homework assignments will get easier as well.
nirvikprantor 11-Jul-19 15:50pm    
i post another solution,that i tried also, can you please check it?
You know how your code should solve the problem, with the debugger, you watch it perform.
You just have to spot when it start to go wrong.
Quote:
If I change the inputs, Answer is showing 0

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
 
Share this answer
 
Comments
nirvikprantor 11-Jul-19 15:59pm    
i post another solution,that i tried also,can you please check it?
Stefan_Lang 12-Jul-19 8:54am    
The code is too long to analyze - remember this is the "quick answers" section. I acan only say it doesn't deliver the best result (which is 4)
To be honest you are missing the skills to provide a good solution, so I really suggest that you take the time and visit the Learn C++ tutorial to understand the language and its potencial in depth.

For your homework you really should use the advantage of C++ and use objects and classes to make your code clearer and better. I would suggest a Airport class like that.
C++
class Airport
{
public:
string name;
int runways;
int delay[10];

int GetMaxDelay();//function
}
You also may use some tools from libraries like vector. This make memory managment easier.

When the answers arent correct than you may have a bug in the code or missed some detail in the implementation. Use the debugger and make output on important steps.
 
Share this answer
 
Comments
Stefan_Lang 12-Jul-19 6:00am    
Good advice, only the public member variables in your example code seems out of place.
nirvikprantor 12-Jul-19 10:42am    
I am trying but I can't solve this problem..
Your code is a bit too long to analyze in full, but it seems your algorithm for assigning planes to runways is off. Your program currently assigns planes like this:
planes 10 (1,1,1,3,3,1,2,2,2,2)
runways	5 (2 2 3 5 7)
capacity (2 2 2 2 2)

Result 5
Time table: ('-' indicates occupied by plane, 'x' indicates last plane left)
runway:|0 1 2 3 4
-------+-+-+-+-+-
time 0:|2 2 2 2 1
time 1:|- - - - 3
time 2:|1 1 3 1 -
time 3:|x x - x -
time 4:|    -   x
time 5:|    x

I'm not sure how you decide what plane to assign to which runway, but there is room for optimization.

I suggest the following algorithm for assigning planes to runways:
1. Determine the highest runway time from all currently unoccupied runways
2. Find the plane with the highest time no larger than this from the list of planes
3. Find the runway with the lowest runway time >= plane time from unoccupied runways
4. assign plane to this runway

This should yield a result of 4 with the following time table:
runway:|0 1 2 3 4
-------+-+-+-+-+-
time 0:|2 2 3 3 2
time 1:|- - - - -
time 2:|2 1 - - 1
time 3:|- x 1 1 x
time 4:|x   x x

Note that this algorithm will not always deliver the best results - I fear that you'd have to test all possible combinations to make sure you always find the best solution. But this algorithm should work well for most cases.

If you want the best algorithm, write a function to enumerate all possible combinations and another to evaluate any given combination. Then test each combination to find the best one.
 
Share this answer
 
Comments
nirvikprantor 12-Jul-19 10:37am    
Planes are all delivering in ascending order...Truely I am trying but can't solve it
Stefan_Lang 12-Jul-19 11:21am    
I don't understand. That doesn't appear to make a lot of sense. What are the time intervals between planes? If there is no time intervall, order does NOT matter!
nirvikprantor 12-Jul-19 10:46am    
Mainly I can't applying the logic...If some of you can send me a sample code..then I can apply it in another way..and so my confusion will be clear...
Stefan_Lang 12-Jul-19 11:29am    
So far, the descriptiono of the task is extremely confusing and, in fact, incomplete. My understanding of what it is that needs to be done is mainly derived from the example, not the description. If you can't provide an accurate description of the task, it's impossible for us to help.
nirvikprantor 12-Jul-19 14:58pm    
In this description the main point is...If we consider the planes delay in the run way above the example,where 2 planes are in each run way then: 1 2 2 3 3
1 1 1
__________
At 1 sec-1st,plane of the 1st,run way which delay time is 1sec,can flay from the run way.so now 1st plane is gone,so on this run way the second plane came in to the 1st position.
same as,in the second run way at 1 sec 1st plane can't take out from the run way...cause its delay time is 2.so at 1sec the plane can go to the middle of the run way..it need another 1 sec to take off from the run way.
That's how we need to find out the total delay time,what total time need to take off all the planes from the run way..an it will be calculate at,(1sec+1sec+1sec+....)=3

1st plane- 1 2 2 3 3
2nd plane- 1 1 1
__________
1sec- 0 1 1 2 2
1sec- 0 0 0 1 1
1sec- 0 0 0 0 0
___________
Total delay=(1+1+1)sec=3 sec

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900