Hostel Visits Problem

#1

How to apply heap on this question ??
I am using vector to store elements and when type 2 query will come then remove the kth position element and print it.

#2

@ashwani225 make a max heap.

  1. for queries of type 1 (insertion)
    i. if there are less than k elements in heap, add the distance as it is
    ii. if there are k elements in the heap, then if if the dist is less than the top element of the heap, remove it from the list and add dist. else, do nothing

This way you will have k smallest distances in each iteration

  1. for queries of type 2, simply output pq.top() as it will be the k largest value till now
#3


test case is not passing

#4

@ashwani225 use long long int as the distance can be very large

#5

ok got it. But I want to ask that how you get this logic because there also be case where heap has less than k elements and type 2 query arrive then what will be printed ??

#6

@ashwani225 there will be no such case, as it is not logically possible. How can they make a query to find the kth nearest hostel without first giving at least k hostels?

Please mark your doubt as resolved in case of no further queries :slight_smile:

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.