Suppose you are given a set of 100m sprint times from the 2020 olympics. The input list has size n and is not sorted, and you may assume that each time is distinct (there are no exact ties). Your team-mate completed in the event, and her time was exactly 10:57 seconds. She returns from the olympics upset, claiming that at least half the competitors had a faster time. Design an algorithm that takes as input the array A consisting of the n sprint times, and outputs the closest n=4 sprint times that are faster than your friend's time. Justify why your algorithm runs in O(n) in the worst case. *For simplicity, you may assume n=4 is an integer
(c) Suppose you are given a set of 100m sprint times from the 2020 olympics. The input list has size n
and is not sorted, and you may assume that each time is distinct (there are no exact ties). Your team-mate
completed in the event, and her time was exactly 10:57 seconds. She returns from the olympics upset,
claiming that at least half the competitors had a faster time. Design an
array A consisting of the n sprint times, and outputs the closest n=4 sprint times that are faster than your
friend's time. Justify why your algorithm runs in O(n) in the worst case.
*For simplicity, you may assume n=4 is an integer
Solution:-
We have to determine the 20 closest times to 10.0 seconds. When we have to find the top x of some array, the most suitable data structure would be Heap.
Let's consider we have to find 'k' closest times(to 10.0) in an array of n values
Step by step
Solved in 3 steps
