Gold Rush - EDITORIAL:
Binary Search, Greedy, Heaps
Given N intervals L_i and R_i specified for each or them, find the maximum length of intersection of K intervals. Let this maximum length found is A. You are given an array M you need to find the element in M which is just less than or equal to A.
Sort intervals based on L_i 's, consider P-consecutive intervals and maintain heap of corresponding P - R_i ’s. Now update the heap and update the maximum intersection length as you iterate through remaining intervals. Do lower bound binary search on array M with max intersection length for finding that particular element in M.
Sort intervals based on L_i ’s. Now Consider first P intervals and construct a min-heap which contains R_i ’s of first k-elements, intersection length is the difference between current L_i and minimum of R_i ’s in the heap, now iterate over remaining L_i ’s in sorted order, whenever you encounter a new L_i replace the min. of heap with the current R_i and do shift-down on heap and update the maximum intersection length. Now after finding maximum length do Lower Bound Binary Search on the array M with this maximum found earlier.
import heapq import bisect import sys input=sys.stdin.readline def main(): m=int(input()) am=[int(j) for j in input().split()] am.sort() for _ in range(int(input())): n,k=[int(j) for j in input().split()] chains=[(0,0) for i in range(n)] for i in range(n): l,r = [int(j) for j in input().split()] chains[i]=(l,r) chains.sort() curr=chains[:k] h=[b for a,b in curr] heapq.heapify(h) ans=max(0,1+h-chains[k-1]) for i in range(k,n): l,r = chains[i] heapq.heapreplace(h,r) ans=max(ans,h-l+1) k1=bisect.bisect_right(am,ans) if k1==0: print(0) else: print(am[k1-1]) if __name__=="__main__": main()