You are attending a party at USC with n other people. Each student i arrives at

Question

You are attending a party at USC with n other people. Each student i arrives at the party at some time si and leaves the party at some time ti (si < ti). Once a person leaves the party, they do not return. Additionally, each student i has a awesomeness factor ci. At all times during the party, you choose to talk to the most awesome student currently at the party (all awesomeness values are distinct.) If someone more awesome arrives at the party, you leave your current conversation partner and talk to the new student. If the person you are talking to leaves the party, you go talk to the most awesome person remaining at the party. (This might or might not be a person with whom you have already talked.) You are the rst to arrive at the party and the last to leave. Additionally, you are the most awesome person at the party (obviously!), so everyone wants to talk with you. Design a data structure which allows you to decide in O(1) time to whom you should talk at any moment. In O(log n) time, you should be able to gure out who arrives or leaves next, and update the data structure appropriately.

Explanation / Answer

try max-heap for the given problem . max-heap will have awesomeness as key. when a person arrives insert the persons awesomeness value into heap. call insert_heap(person_awesome_vale,Heap) when a persons enters a party. // where Heap is the array of some predefined number. call delete_heap(Heap) when a person leaves a party. call max_heap(Heap) to get the person having most awesomeness value to talk to. since this is a heap , you can get the max awesome person in O(1) time, because the maximal element is the root of the heap. when a person leaves you have to reconfigure the heap ,so this will take O(log n) ( cost of applying max_heapify( see cormen book ). when a person enters you have to configure heap ,this will take O(log n ) time ,by applying max_heapify. you can see that whenever a person having awesomeness more than any other person in the room ,then it becomes the root of the element,and the previous person becomes its one of children. by applying max_heap op you can get the person to talk. when a person leaves ,we reconfigure the heap so the person having highest awesomeness among remaining person comes at root of heap. for implementation use introduction to algo by cormen ( heap chapter ).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.