FastPrep
Problem · Intervals

Smallest Set Covering Intervals

Learn this problem
● HardSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

Given a series of integer intervals, determine the size of the smallest set that contains at least 2 integers within each interval.

Function

interval(first: int[], last: int[]) → int

Complete the function interval in the editor.

interval has the following parameters:

  1. 1. int first[n]: each element represents the start of intervali
  2. 2. int last[n]: each element represents the end of intervali

Returns

int: the size of the smallest interval possible

Examples

Example 1

first = [0, 1, 2]last = [2, 3, 3]return = 3
Example 1 illustration
The intervals start at first[i] and end at last[i]. Both intervals 0 and 1 contain 1 and 2. These are the only two integers that interval 0 shares, so both integers must be included in the answer set. Both intervals 1 and 2 contain 2 and 3. These are the only two values that interval 2 shares. The smallest set that contains at least 2 integers from each interval is {1, 2, 3}.

Constraints

  • 1 ≤ n ≤ 105
  • 0 ≤ first[i] ≤ last[i] ≤ 109

More Snowflake problems

drafts saved locally
public int interval(int[] first, int[] last) {
    // write your code here
}
first[0, 1, 2]
last[2, 3, 3]
expected3
checking account