|
Given a 2D array arr of size N which represents an interval [start, end] inclusive where (start < end), the task is to add only one interval of minimum size (size = end – start) into the given arr, such that merging all the interval result in only one interval.
Examples:
Input: arr= {{12, 20}, {24, 100}}
Output: 4
Explanation: We can add the interval [20, 24] which is the smallest possible interval.
Input: arr= {{21, 43}, {26, 29}, {46, 70}}
Output: 3
Approach: Greedy algorithm:
The idea to solve this problem is that we’ll try to add intervals greedily. Since we know there is a single interval missing, we want to track the gap when adding the intervals in a sorted manner from start to end.
We can do this by keeping the track of the last interval’s end and new interval’s begin when the previous and the current intervals are non overlapping.
Follow the steps below to implement the above idea:
- First sort the intervals based on start position.
- Keep variables “start” and “end”, which stores the starting and ending point of our required answer interval. and an extra variable “prev” for storing the last occurred interval in the iteration that is needed to merge for the next upcoming intervals.
- Check if intervals overlapped or not.
- If Intervals are not overlapped
- Keep track of “start” and “end”
- Update the “prev” with current interval arr[i].
- Update “prev” after merging the overlapping intervals
- Return the size of the interval using the end-start.
Below is the implementation of the above approach:
C++
<?php
function minInterval($arr) {
sort($arr);
$n = count($arr);
$start = -1;
$end = -1;
if ($n == 0 || $n == 1)
return 0;
$prev = $arr[0];
for ($i = 1; $i < $n; $i++) {
if (max($arr[$i][0], $prev[0])
> min($arr[$i][1], $prev[1])) {
if ($start == -1) {
$start = $prev[1];
$end = $arr[$i][0];
}
else {
$end = $arr[$i][0];
}
$prev = $arr[$i];
}
else {
$prev = array( min($arr[$i][0], $prev[0]),
max($arr[$i][1], $prev[1]) );
}
}
return $end - $start;
}
$arr = array(array(12, 20), array(24, 100));
$result = minInterval($arr);
echo $result;
?>
|
Time Complexity: O(N * logN), This is due to sorting.
Auxiliary Space: O(1)
|
