FastPrep
Problem · Intervals

Minimum Segments

Learn this problem
● MediumSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

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

minimumDivision(a: int[], b: int[], k: int) → int

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.

Examples

Example 1

a = [1, 2, 5, 10]b = [2, 4, 8, 11]k = 2return = 2
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

  • 1 ≤ n ≤ 2 * 105
  • 1 ≤ a[i] ≤ b[i] ≤ 109
  • 1 ≤ k ≤ 109

More Snowflake problems

drafts saved locally
public int minimumDivision(int[] a, int[] b, int k) {
  // write your code here
}
a[1, 2, 5, 10]
b[2, 4, 8, 11]
k2
expected2
checking account