Restore A Shuffled Queue As Per Given Conditions In C++

In this article, we will discuss how to restore a shuffled queue as per given conditions in C++ with its algorithm and implementation.

Problem Statement:

Considering two arrays , A and B, and N individuals waiting in line. The name of the individual is represented by array A, and the number of people taller than the individual standing in front of it is represented by array B. Now, the line is rearranged. Printing the queue's initial sequence while adhering to the aforementioned property is the task.

Algorithm:

Step 1: Create an array called "pairs" to hold the pair of names of the individuals and their assigned numbers.

Step 2: Combine the values from the persons and nums arrays into the pairs array by iterating through them.

Step 3: In order to sort the pairs array, use the sort function.

Step 4: Moreover, in this step we define the 'res' list and begin iterating through the pairs array.

Step 5: Since obtaining the original queue is impossible, print -1 if p - pairs[p].first is less than 0.

Step 6: If not, update the temp field in the res[p].

Step 7: Currently, we must modify the individual's location within the res[q] collection. Enter the 'res' array and begin exploring it.

Step 8: Go from index 0 to index q through the res array using the nested loop.

Step 9: Increase res[q] by 1 if it is greater than or equal to res[p].

Step 10: Print out each person's position.

Input: N = 4, A = {'a', 'b', 'c', 'd'}, B = {0, 2, 0, 0}

Output:

Observing the output queue and the heights at which they were generated, it is clear that:

✅ The person with the 0th index is in front of a because he is the first person in line. Thus, in the input, is linked to 0.
✅ Only a stands in front of c, but a is shorter than c. As a result, in the input, c is connected to 0.
✅ Although c and a are in front of d, d is taller than them both. As a result, in the input, d is linked to 0.
✅ d, c, and a are in front of b. However, only d and c are higher than b. Therefore, in the input, b is related to 2.

Example 1:

Let us take an example to illustrate how to restore a shuffled queue as per given conditions in C++ .

Example


#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

// Function to restore the shuffled queue
void restoreShuffledQueue(char names[], int positions[], int size) {
    // Creating a pair to store names and positions
    pair<int, string> person[size];

    // Array to store the final order
    int finalOrder[size];
    bool isPossible = true;

    // Storing names and positions in the pair
    for (int i = 0; i < size; i++) {
        person[i].second = names[i];
        person[i].first = positions[i];
    }

    // Sorting the pair based on positions
    sort(person, person + size);

    // Traverse the pairs
    for (int i = 0; i < size; i++) {
        int newPosition = i - person[i].first;

        // If it is not possible to generate the Queue
        if (newPosition < 0) {
            cout << "-1";
            isPossible = false;
        }

        if (!isPossible)
            break;
        else {
            finalOrder[i] = newPosition;

            // Adjusting positions
            for (int j = 0; j < i; j++) {
                if (finalOrder[j] >= finalOrder[i])
                    finalOrder[j]++;
            }
        }

        // Finally printing the restored queue
        if (i == size - 1 && isPossible) {
            for (int i = 0; i < size; i++) {
                cout << person[i].second << " " << finalOrder[i] + 1 << endl;
            }
        }
    }
}

// Main Code
int main() {
    int size = 4;

    // Names of persons
    char names[size][20] = {"John", "Alice", "Bob", "Eve"};

    // Associated positions
    int positions[size] = {0, 2, 0, 0};

    // Function Call
    restoreShuffledQueue(*names, positions, size);
    return 0;
}

Output:

Output


J 1
h 3
n 4
o 2

Example 2:

Let us take their example to illustrate how to restore a shuffled queue as per given conditions in C++.

Example


#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

// Function to find the original queue
void restoreOriginalQueue(string names[], int tallerCount[], int size) {
    pair<int, string> pairs[size];
    int originalOrder[size];

    // Insert elements into pairs[] array
    for (int i = 0; i < size; i++) {
        pairs[i].first = tallerCount[i];
        pairs[i].second = names[i];
    }

    // Sort the pairs[] array
    sort(pairs, pairs + size);

    // Calculate the temporary positions and check for validity
    for (int i = 0; i < size; i++) {
        int temp = i - pairs[i].first;

        // Not possible to create the original queue
        if (temp < 0) {
            cout << "It is not possible to create the original queue" << endl;
            return;
        }

        originalOrder[i] = temp;
    }

    // Update the temporary positions to handle multiple people with the same number of taller people in front
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < i; j++) {
            if (originalOrder[j] >= originalOrder[i])
                originalOrder[j]++;
        }
    }

    // Printing the original queue
    cout << "The original queue is:" << endl;
    for (int i = 0; i < size; i++) {
        cout << pairs[i].second << " " << originalOrder[i] + 1 << endl;
    }
}

int main() {
    int size = 4;

    // Person names
    string names[size] = {"Harsha", "vardhan", "sham", "Ram"};

    // Number of taller people
    int tallerCount[size] = {0, 1, 0, 0};

    // Function Call
    restoreOriginalQueue(names, tallerCount, size);

    return 0;
}

Output:

Output


The original queue is:
Harsha 1
Ram 2
sham 4
vardhan 3

Problem Statement:

Algorithm:

Example 1:

Example 2:

Input Required