You are given a set of elements to be inserted into a priority queue. Each element is represented in the format (x, y), where x is the element's value, and y is its priority. Higher values od y indicate higher priority. If two element share the same priority, the element with lesser value takes precedence.
Your task is to write a program to print x value of the remaining element in the queue after deleting K elements from the queue in the ascending order of their priority.
Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings while reading the input or while printing, as these contribute to the standard output.
Constraits:
(i) x and y should be positive
Input Format:
The first input line contains N, where N denotes the number of elements.
Next N lines of input contains x y where x is the element and y is its priority.
The last input line contains K where K denotes the number of elements to be removed from the queue.
Output Format:
The output cotains the element that are not deleted from the queue. Print x values in the ascending orderof their priority.
Sample input 1:
5
2 4
5 3
6 1
7 4
9 4
3
Sample Output 1:
6 5
Explanation 1:
From the given sample input 1 we have
Total number of elements is 5
total number of elements to be deleted is 3
So clearly 2, 7 and 9 have the highest priority as 4 so it will get deleted and the remaining elements are 6, 5 are printed in the ascending order of their priority.
Sample input 2:
4
3 7
5 7
8 7
7 4
2
Sample Output 2:
7 8
Explanation 2:
From the given sample input 2 we have
Total number of elements are 4
Total number of elements to be deleted is 2
So clearly 3 and 5 have the highest priority and it is 7, so they will get deleted and the remaining elements are 7, 8 are printed in the ascending order of their priority.
Do you dream of turning your thoughts and words into income ? join us now and become blogger now.
#python 3 code
from collections import defaultdict
def delete_elements(queue, num_to_delete):
priority_dict = defaultdict(list)
for element, priority in queue:
priority_dict[priority].append(element)
sorted_priority_dict = sorted(priority_dict.items(), reverse=True)
deleted_elements = []
for priority, elements in sorted_priority_dict:
if num_to_delete >= len(elements):
deleted_elements.extend(elements)
num_to_delete -= len(elements)
else:
deleted_elements.extend(elements[:num_to_delete])
break
remaining_elements = [pair for pair in queue if pair[0] not in deleted_elements]
remaining_elements.sort(key=lambda x: x[1])
print(" ".join(str(element) for element, _ in remaining_elements))
N = int(input())
queue = []
for _ in range(N):
x, y = map(int, input().split())
queue.append((x, y))
K = int(input())
delete_elements(queue, K)
0 Comments
Leave a Comment