DPWORLD Coding Question – Solved

Given a series of integer intervals, determine the size of the smallest set that contains at least 2 integers within each interval. Example: first = [0, 1, 2] last = [2, 3, 3] The intervals start at first[i] and end at last[i]. - Interval 0: [0, 2] → contains 1 and 2 - Interval 1: [1, 3] → contains 2 and 3 - Interval 2: [2, 3] → contains 2 and 3 To satisfy all intervals, we must select integers such that each interval has at least 2 of them. The smallest such set is {1, 2, 3}, and the answer is 3. Function Description Complete the function `interval` with the following parameters: - `int first[]`: each element represents the start of interval[i] - `int last[]`: each element represents the end of interval[i] Returns: - `int`: the size of the smallest set such that every interval contains at least two integers from it Constraints: - 1 ≤ n ≤ 10^5 - 0 ≤ first[i] < last[i] ≤ 10^9 Input Format for Custom Testing: The first line contains the integer n, the number of intervals. The second line contains n integers representing the array `first`. The third line contains n integers representing the array `last`. Sample Input 0 4 3 2 0 4 5 4 2 6 Explanation: The intervals are: - [3, 5] - [2, 4] - [0, 2] - [4, 6] The smallest set containing at least 2 integers in each interval might be {1, 2, 3, 4, 5}. The correct set would be calculated by the function, and its size would be returned.