FastPrepFastPrep
Problem Brief

Smallest Set Covering Intervals

INTERNOA

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

Function Description

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

1Example 1

Input
first = [0, 1, 2], last = [2, 3, 3]
Output
3
Explanation
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

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 105
  • 0 ≤ first[i] ≤ last[i] ≤ 109
public int interval(int[] first, int[] last) {
    // write your code here
}
Input

first

[0, 1, 2]

last

[2, 3, 3]

Output

3

Sign in to submit your solution.