In this tutorial, we will explore the process of reconstructing a shuffled queue based on specific criteria in C++, including the algorithm and its practical application.
Problem Statement:
When dealing with two arrays, A and B, and a total of N people queued up, each person's name is denoted by array A, and the count of people taller than that person in front of them is indicated by array B. The objective is to reorder the line in a manner that maintains the specified condition and then display the original sequence of the queue.
Algorithm:
Create an array named "pairs" to store the combination of names of the people and the corresponding numerical assignments.
Step 2: Merge the values from the persons and nums arrays into the pairs array by iterating over each of them.
Step 3: To arrange the elements in the pairs array in a specific order, employ the sort method.
In this step, we will establish the 'res' list and commence the process of iterating through the pairs array.
If it's not feasible to retrieve the initial queue, output -1 when the difference between p and pairs[p].first is negative.
If not, proceed to modify the temp field within the res[p] data structure.
Step 7: At this point, it is necessary to adjust the position of the specific item within the res[q] array. Access the 'res' array and commence investigating its contents.
Step 8: Iterate from index 0 to index q within the res array by utilizing the nested loop.
Step 9: Increment res[q] by 1 if it is equal to or greater than res[p].
Step 10: Print out each person's position.
Given an integer N equal to 4, and two arrays A containing elements {'a', 'b', 'c', 'd'} and B containing values {0, 2, 0, 0}, we have the following data.
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's consider an example to demonstrate the process of reordering a shuffled queue based on specified criteria in C++.
#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:
J 1
h 3
n 4
o 2
Example 2:
Let's consider their instance to demonstrate the process of reconstructing a randomized queue based on specified criteria in C++.
#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:
The original queue is:
Harsha 1
Ram 2
sham 4
vardhan 3
