Description
Solutions
Submission
Smallest Set Covering Intervals
🤘 INTERN

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

Example 1: 

Input:  first = [0, 1, 2], last = [2, 3, 3]
Output: 3 
Explanation:

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
Thumbnail 0
Testcase
Result
Case 1

input:

output: