Problem Statement:

You have n people standing in a line. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Solution:

The problem can be solved by using sorting and inserting elements into the list at the corresponding index.

1. Sort the list in decreasing order of height, if two persons have the same height then sort them in increasing order of 'k'.

2. Initialize an empty list 'result'.

3. Traverse through each element in the sorted list, and insert the element at the index 'k' of the 'result' list.

4. Return the 'result' list.

Code:

def reconstructQueue(people):

# Sort the list in decreasing order of height and in increasing order of k.
people.sort(key=lambda x: (-x[0], x[1]))

result = []

# Traverse through each element and insert it at the index k of the result list.
for person in people:
    result.insert(person[1], person)

return result

Test the function

people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] print(reconstructQueue(people))

Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

The time complexity of the above algorithm is O(n^2), where n is the number of persons in the queue. This is because we use insert operation in the result list for n elements, which has a time complexity of O(n) in the worst case. However, as the maximum number of insertions can be only n, the worst case time complexity of the algorithm can be approximated as O(nlogn).

1