Cutting Intervals
Time limit2sMemory limit128 MB
Given N intervals, find cut points A and B minimizing A then B so the total overlapped length inside [A,B] equals exactly K, or output 0 0.
- Level
Medium6 of 10
- Topics
- Binary search, Prefix sum, Two pointers
- Solved
- No attempts yet
Problem
You are given N intervals on a number line. Choose two integers A and B(A < B). For each interval, keep only the part that lies between A and B and cut away the rest. Find A and B so that the total length of all remaining parts is exactly K.
Input
The first line contains two integers N and K(1 <= N <= 1,000, 1 <= K <= 1,000,000,000).
Each of the next N lines contains the left and right endpoint positions of one interval. Every endpoint position is an integer from 0 to 1,000,000, inclusive.
Output
Print two integers A and B separated by a space. If no pair satisfies the condition, print 0 0.
If there are multiple valid pairs, print the one with the smallest A. If there are still multiple pairs, print the one with the smallest B.