Gold Rush - EDITORIAL:
Author: karthikeya619
Editorialist: karthikeya619
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Binary Search, Greedy, Heaps
PROBLEM:
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.
QUICK EXPLANATION:
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.
EXPLANATION:
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.
TIME COMPLEXITY:
O(T(NlogN+logM))
SOLUTIONS:
Setter's Solution
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[0]-chains[k-1][0])
for i in range(k,n):
l,r = chains[i]
heapq.heapreplace(h,r)
ans=max(ans,h[0]-l+1)
k1=bisect.bisect_right(am,ans)
if k1==0:
print(0)
else:
print(am[k1-1])
if __name__=="__main__":
main()