Problem Link:
Author: tseccodecell
DIFFICULTY :
Easy-Medium
PRE-REQUISITES:
Sorting, Priority Queue, Array Traversal
PROBLEM:
Given a list of N people, you have to choose M of them in the following way:
At each of the M iterations, select one from beginning or end according to priority basis given below and delete the selected from the list
Continue this process till M iterations are complete
After the people are selected, order them on the basis of priority:
- Highest priority : Less age
- Medium Priority : Lexicographic ordering of name
- Lowest priority : Less index
Then display their indexes in original list after ordering
EXPLANATION:
Many data structures can be used to store original list, even simple array
but using a double ended queue for such type of operations is easier to understand and visualize
Select candidates according to the priority(you can use a comparision function) then delete them from the list and put them in another list
Finally, sort the selected list of candidates according to priority basis using merge sort, as it has good complexity for sorting$(O(nlogn))$
Inbuilt sort function can be used to perform this easily
A comparision function can be passed to the sort function(this is supported in many programming languages) to perform this operation easily
Alternative Solution:
You can put elements in priority queue after deleting them and then display the elements in priority queue as required by popping the elements to another list(the elements will be ordered according to priority)
Some test cases with answers:
Input:
4
10 5
ksz 20
whn 20
whn 20
lsa 20
bcoxh 20
dqiw 20
lsa 20
lsa 20
kzd 20
febdb 20
10 7
xvfbc 67
xvfbc 25
xvfbc 37
xvfbc 39
xvfbc 64
xvfbc 30
xvfbc 54
xvfbc 68
xvfbc 52
xvfbc 58
10 6
a 27
o 26
yzp 60
jlf 58
trkdc 37
trkdc 55
yzp 42
gub 25
trkdc 37
yzp 66
10 5
rzbm 28
mgqo 52
mgqo 61
txdk 45
rzbm 29
rzbm 21
xcok 25
rzbm 46
x 40
swnkk 60
Output:
9 0 8 6 7
1 2 3 8 9 4 0
1 0 4 5 3 2
0 8 7 1 9
Time Complexity: O(n + m + mlogm) = O(n + mlogm)
Time complexity also depends on comparision time but not much