 # Gold Rush - EDITORIAL:

Practice

Contest

Author: karthikeya619

Editorialist: karthikeya619

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.

O(T(NlogN+logM))

# SOLUTIONS:

Setter's Solution
``````import heapq
import bisect
import sys
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()
``````