FastPrepFastPrep
Problem Brief

Minimum Segments

INTERNOA
See Snowflake online assessment and hiring insights

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. 1. int a[n]: an integer array of first parameters of intervals
  2. 2. int b[n]: an integer array of second parameters of intervals
  3. 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.

1Example 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)

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 2 * 105
  • 1 ≤ a[i] ≤ b[i] ≤ 109
  • 1 ≤ k ≤ 109
public int minimumDivision(int[] a, int[] b, int k) {
  // write your code here
}
Input

a

[1, 2, 5, 10]

b

[2, 4, 8, 11]

k

2

Output

2

Sign in to submit your solution.