PROBLEM LINK:
Setter: Misha Chorniy
Tester: Rajat De
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Segment Intersection and Sorting.
PROBLEM:
Given N segments [L_i, R_i], find the length of maximum length segment intersection between any subset of size K of segments.
SUPER QUICK EXPLANATION
- Sort the segments by the left end in non-decreasing order and if the left end is same, sort by the right end in non-increasing order.
- Fix the starting point, say S, and considering all segments starting before or at S, suppose we have the endpoints of these segments. Then K-th from rightmost direction is the maximal right end, say E for given starting point. Fix left end of all segments as the starting point and find out K-th rightmost end. The answer is just max(S-E) for all values of S.
EXPLANATION
First of all, we know, that intersection of any subset of segments will both begin with the start point of a segment in the subset as well as end with some segment in the subset.
So, based on this, we can make a solution, by sorting all segments by their left end. Fix the left end of the current segment, say S as the left end, and considering all segments starting before or at S, we get a multiset of right ends. Since we want the length of the maximal intersection, we want to choose as larger right end as possible while having K segments in the set. So, we look for Kth rightmost end from all segments which started before S. Say this value is E. Hence, length of intersection is E-S. We can find the maximum value of E-S for all left ends of segments S.
This way, we can develop a brute solution, which considers every contiguous subset of size K of segments when sorted in increasing order of left ends. This gives time complexity O(N*K+N*logN) which will time out.
But, we can notice, that if we have the segments sorted by the left end in non-decreasing order, the set of segments will only extend to the right as we move the starting point to the right. This helps us in realizing, that we do not need to handle each start point separately.
We have a set of positions, and we need to find the Kth largest element from it. Elements are only added to this set. We can simply use an ordered set or using min-heap, this can be done. In min heap, whenever the size of the set exceeds K, remove the segment’s right end, which is ending earliest. The reason being, only by deleting the earliest ending segment we can get the segment intersection to be maximum. Also, the top element of min heap will give kth largest element, if the size of the heap is K.
So, the final solution is to make a min heap and add right ends to heap as we shift left end forward. Take the maximum of E-S and print the answer.
Time Complexity
Time complexity is O(N*logN) per test case, sorting takes O(N*logN), heap operations take O(logK).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 