Given is an array consisting of n intervals. The ith interval is of type
(a[i], b[i]). Also given is an integer k. Add exactly one segment
(a, b) to the array such that b - a ≤ k and the modified array can
be separated into the minimum number of connected sets.
A set of segments (a[1], b[1]), (a[2], b[2]), ...,
(a[n], b[n]) is connected if every point in the segment
(min(a[1], a[2], ..., a[n]), max(b[1], b[2], ..., b[n])) is covered by some segment
(a[i], b[i]) in the set.
Function Description
Complete the function minimumDivision in the editor.
minimumDivision has the following parameters:
- 1.
int a[n]: an integer array of first parameters of intervals - 2.
int b[n]: an integer array of second parameters of intervals - 3.
k: an integer denoting the maximum range of the segment that can be added
Returns
int: an integer denoting the minimum number of sets needed to separate the array after adding one segment.
Example 1:
Input: a = [1, 2, 5, 10], b = [2, 4, 8, 11], k = 2
Output: 2
Explanation:The original intervals are (1, 2), (2, 4), (5, 8), (10, 11). Add the segment (4, 5) into the array since 5 - 4 ≤ 2. After that, we can separate the array into 2 connected sets: - (1, 2), (2, 4), (4, 5), (5, 8) - (10, 11)
- 1 ≤ n ≤ 2 * 105
- 1 ≤ a[i] ≤ b[i] ≤ 109
- 1 ≤ k ≤ 109
input:
output: