Merging Intervals#3540
Given a list of integer intervals, your task is to determine the -th number in the list when all numbers are sorted in non-decreasing order (with indexing starting from ). Each interval is defined by two numbers, representing the inclusive lower and upper bounds of that interval.
For instance, the intervals and correspond to the list of numbers \{1, 2, 3, 5, 6, 7\}. Note that a number can appear in multiple intervals: for example, the intervals and yield the list \{1, 2, 3, 3, 4, 4, 5\}.
The first line contains an integer (1 \le p \le 50), representing the number of intervals. The following lines each contain two integers: lowerBound and upperBound, which define the bounds of an interval. It is guaranteed that lowerBound \le upperBound and -2 \times 10^9 \le lowerBound, upperBound \le 2 \times 10^9.
The final line contains the integer (0 \le n \le 2 \times 10^9). The input is guaranteed to be valid, meaning the -th element always exists.
Print the -th number in the list when all numbers are sorted in non-decreasing order.
Example 1