Wait Time, Food Time, and Tips for Customers at Your Restaurant

You have a Restaurant and there is a Array nums [ ] of N people outside your restaurant.
Your, waiter found out that for each valid i, the i-th person gave Ai Tip. Waiter treats person based on their Tip. I.e., a person with a higher Tip is always treated before any person with a lower Tip, waiter is also fair.
So he treats person with an equal Tip based on their position in the array, i.e. a person ahead in the array is always treated before a person with the same Tip that is further behind in the array.

The first person has to wait an hour for waiter to cook his food /order.
To finished food for each person also takes an hour, and waiter always starts cooking for the next person as soon as current person done with his food.

Find out For each person, find out how long time (in hours) needs to wait to get and also finished his food and also how much Tip you get.

Examples:

Input: N=5 , nums[ ]={4, 5, 7, 5, 6}

Output: 5, 3, 1, 4, 2 , Tip = 27

Explanation: Person number 3 has the highest Tip. Therefore, this person just waits an hour for waiter to cook his order. Person number 5 has the next highest tip, so they go next. They need to wait an hour for person 3 to be finished his food. In total, person 5 has to wait 2 hours. After that, both persons 2 and 4 have an equal tip, but person 2 is ahead in the array, so person 2 goes next, followed by person 4, and then finally person1 and tip you get is 27.

Input: N=4 , nums[ ]= { 8, 9, 8, 9 }

Output: 3 1 4 2, Tip = 34

Approach:
This is implementation based question every time find out person with highest Tip and treat first as compare to low Tip person.
Use Sorting to get max Tip value person for knowing tip you just all tip you get by people that’s it.

Below is the implementation of the above approach:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to chek how much Tip you Get
void Tipget(vector<int>& v1)
{
    int sum = 0;
    int n = v1.size();
    for (int i = 0; i < n; i++) {
        sum += v1[i];
    }
    cout << ", Tip = " << sum << endl;
}
// function to return ans
vector<int> Towait(vector<int>& v1)
{
    vector<int> v2 = v1;
    sort(v2.begin(), v2.end());
    // intialized ans vector with zero
    vector<int> ans(v1.size(), 0);
    int count = 1;
    for (int i = v1.size() - 1; i >= 0; i--) {
        int temp = v2[i];
        for (int j = 0; j < v1.size(); j++) {
            if (v1[j] == temp && ans[j] == 0) {
                ans[j] = count;
                break;
            }
        }
        count++;
    }
    return ans;
}
// function to print array
void printarray(vector<int>& a)
{
    // size of the vector
    int n = a.size();
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
}
// Driver Code
int main()
{
    vector<int> v1 = { 4, 5, 7, 5, 6 };
    vector<int> ans = Towait(v1);
    printarray(ans);
    Tipget(v1);
    return 0;
}

Output:

5 3 1 4 2 , Tip = 27

Time complexity:

Calculating the sum of vector elements takes O(n) time (n is vector size).
Sorting the vector with 'sort' takes O(nlogn) time.
Nested loop for 'ans' vector takes O(n^2) time in worst case.
Sorting dominates O(nlogn), so overall complexity is O(n^2).

Space complexity:

Input vector 'v1' uses O(n) space (n is input size).
Extra space for 'v2' and 'ans' vectors also uses O(n) space.
Total space complexity is O(n) due to input and extra vectors.

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.