PROBLEM LINK-: CLICK HERE
PROBLEM SETTERS-: @aliencoder_07 @dcpandey
EDITORIALIST-: @dcpandey
DIFFICULTY-: MEDIUM
PREREQUISITES-: Segment Intersection and sorting.
PROBLEM-: Zenny has a difficult problem to solve. She has N segments [l1,r1],[l2,r2],…,[lN,rN] on the x-axis. A K-subset of these N segments consists of any K of these segments. For each K-subset, consider the common intersection of all the K segments, i.e. the set of points which belong to each of the K segments. The intersection of segments is also a segment; the length of a segment [l,r] is r−l. Zenny is asking you to find the maximum of lengths of the common intersections in all K-subsets.
EXPLANATION-: Sort the segments by the left end in non-decreasing order and if the left end is the same, sort by the right end in non-increasing order.
Fix the starting point, say SS, and considering all segments starting before or at SS, suppose we have the endpoints of these segments. Then K-th from the rightmost direction is the maximal right end, say EE for the given starting point. Fix the left end of all segments as the starting point and find out K-th rightmost end. The answer is just max(S-E)max(S−E) for all values
SOLUTION-: CLICK HERE