Dado un conjunto de intervalos que no se superponen y un nuevo intervalo, inserte el intervalo en la posición correcta. Si la inserción da como resultado intervalos superpuestos, fusione los intervalos superpuestos. Suponga que el conjunto de intervalos que no se superponen se ordena en función de la hora de inicio, para encontrar la posición correcta de inserción.
Requisito previo: fusionar los intervalos
Ejemplos:
Input: Set : [1, 3], [6, 9]
New Interval : [2, 5]
Output: [1, 5], [6, 9]
The correct position to insert new interval
[2, 5] is between the two given intervals.
The resulting set would have been
[1, 3], [2, 5], [6, 9], but the intervals
[1, 3], [2, 5] are overlapping. So, they are
merged together in one interval [1, 5].
Input: Set : [1, 2], [3, 5], [6, 7], [8, 10], [12, 16]
New Interval : [4, 9]
Output: [1, 2], [3, 10], [12, 16]
First the interval is inserted between intervals
[3, 5] and [6, 7]. Then overlapping intervals are
merged together in one interval.
Método 1: Análisis de todos los casos
Enfoque:
Suponga que el nuevo intervalo que se insertará es: [a, b]
Caso 1: b < (hora de inicio del primer intervalo en el conjunto)
En este caso, simplemente inserte el nuevo intervalo al comienzo del conjunto.
Caso 2: (valor final del último intervalo del conjunto) < a
En este caso, simplemente inserte un nuevo intervalo al final del conjunto.
Caso 3 : un ? (valor inicial del primer intervalo) y b ? (valor final del último intervalo)
En este caso, el nuevo intervalo se superpone con todos los intervalos, es decir, contiene todos los intervalos. Así que la respuesta final es el nuevo intervalo en sí.
Caso 4: el nuevo intervalo no se superpone con ningún intervalo del conjunto y se encuentra entre dos intervalos cualesquiera del conjunto
En este caso, simplemente inserte el intervalo en la posición correcta en el conjunto. Un ejemplo de caso de prueba para esto es:
Input: Set : [1, 2], [6, 9]
New interval : [3, 5]
Output: [1, 2], [3, 5], [6, 9]
Caso 5: El nuevo intervalo se superpone con el(los) intervalo(s) del conjunto.
En este caso, simplemente combine el nuevo intervalo con intervalos superpuestos. Para comprender mejor cómo combinar intervalos superpuestos, consulte esta publicación: Combinar intervalos superpuestos
El ejemplo 2 de casos de prueba de muestra anteriores cubre este caso.
C++
// C++ Code to insert a new interval in set of sorted
// intervals and merge overlapping intervals that are
// formed as a result of insertion.
#include <bits/stdc++.h>
using namespace std;
// Define the structure of interval
struct Interval
{
int start;
int end;
Interval()
: start(0), end(0)
{
}
Interval(int s, int e)
: start(s), end(e)
{
}
};
// A subroutine to check if intervals overlap or not.
bool doesOverlap(Interval a, Interval b)
{
return (min(a.end, b.end) >= max(a.start, b.start));
}
// Function to insert new interval and
// merge overlapping intervals
vector<Interval> insertNewInterval
(vector<Interval>& Intervals, Interval newInterval)
{
vector<Interval> ans;
int n = Intervals.size();
// If set is empty then simply insert
// newInterval and return.
if (n == 0)
{
ans.push_back(newInterval);
return ans;
}
// Case 1 and Case 2 (new interval to be
// inserted at corners)
if (newInterval.end < Intervals[0].start ||
newInterval.start > Intervals[n - 1].end)
{
if (newInterval.end < Intervals[0].start)
ans.push_back(newInterval);
for (int i = 0; i < n; i++)
ans.push_back(Intervals[i]);
if (newInterval.start > Intervals[n - 1].end)
ans.push_back(newInterval);
return ans;
}
// Case 3 (New interval covers all existing)
if (newInterval.start <= Intervals[0].start &&
newInterval.end >= Intervals[n - 1].end)
{
ans.push_back(newInterval);
return ans;
}
// Case 4 and Case 5
// These two cases need to check whether
// intervals overlap or not. For this we
// can use a subroutine that will perform
// this function.
bool overlap = true;
for (int i = 0; i < n; i++)
{
overlap = doesOverlap(Intervals[i], newInterval);
if (!overlap)
{
ans.push_back(Intervals[i]);
// Case 4 : To check if given interval
// lies between two intervals.
if (i < n &&
newInterval.start > Intervals[i].end &&
newInterval.end < Intervals[i + 1].start)
ans.push_back(newInterval);
continue;
}
// Case 5 : Merge Overlapping Intervals.
// Starting time of new merged interval is
// minimum of starting time of both
// overlapping intervals.
Interval temp;
temp.start = min(newInterval.start,
Intervals[i].start);
// Traverse the set until intervals are
// overlapping
while (i < n && overlap)
{
// Ending time of new merged interval
// is maximum of ending time both
// overlapping intervals.
temp.end = max(newInterval.end,
Intervals[i].end);
if (i == n - 1)
overlap = false;
else
overlap = doesOverlap(Intervals[i + 1],
newInterval);
i++;
}
i--;
ans.push_back(temp);
}
return ans;
}
// Driver code
int main()
{
vector<Interval> Intervals;
Interval newInterval;
newInterval.start = 1;
newInterval.end = 2;
Intervals.push_back(newInterval);
newInterval.start = 3;
newInterval.end = 5;
Intervals.push_back(newInterval);
newInterval.start = 6;
newInterval.end = 7;
Intervals.push_back(newInterval);
newInterval.start = 8;
newInterval.end = 10;
Intervals.push_back(newInterval);
newInterval.start = 12;
newInterval.end = 16;
Intervals.push_back(newInterval);
newInterval.start = 4;
newInterval.end = 9;
vector<Interval> ans =
insertNewInterval(Intervals, newInterval);
for (int i = 0; i < ans.size(); i++)
cout << ans[i].start << ", "
<< ans[i].end << "\n";
return 0;
}
Producción
1, 2 3, 10 12, 16
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método 2: Usar intervalos de fusión
- Agregue el intervalo dado a la lista dada de los intervalos.
- Ahora se convierte en el mismo viejo problema de intervalos de fusión. Para comprender mejor cómo combinar intervalos superpuestos, consulte esta publicación: Combinar intervalos superpuestos
- Utilice la función de fusión de intervalos.
C++
// C++ Code to insert a new interval in set of sorted
// intervals and merge overlapping intervals that are
// formed as a result of insertion.
#include <bits/stdc++.h>
using namespace std;
// Define the structure of interval
struct Interval
{
int s, e;
};
// A subroutine to check if intervals overlap or not.
bool mycomp(Interval a, Interval b) { return a.s < b.s; }
// merge overlapping intervals
void insertNewInterval(vector<Interval>& Intervals, Interval newInterval)
{
vector<Interval> ans;
int n = Intervals.size();
Intervals.push_back(newInterval); //Insert the new interval into Intervals
sort(Intervals.begin(), Intervals.end(), mycomp);
int index = 0;
// Traverse all input Intervals
for (int i = 1; i <=n; i++) {
// If this is not first Interval and overlaps
// with the previous one
if (Intervals[index].e >= Intervals[i].s) {
// Merge previous and current Intervals
Intervals[index].e = max(Intervals[index].e, Intervals[i].e);
}
else {
index++;
Intervals[index] = Intervals[i];
}
}
for (int i = 0; i <= index; i++)
cout << Intervals[i].s << ", " << Intervals[i].e << "\n";
}
// Driver code
int main()
{
vector<Interval> Intervals;
Interval newInterval;
newInterval.s = 1;
newInterval.e = 2;
Intervals.push_back(newInterval);
newInterval.s = 3;
newInterval.e = 5;
Intervals.push_back(newInterval);
newInterval.s = 6;
newInterval.e = 7;
Intervals.push_back(newInterval);
newInterval.s = 8;
newInterval.e = 10;
Intervals.push_back(newInterval);
newInterval.s = 12;
newInterval.e = 16;
Intervals.push_back(newInterval);
newInterval.s = 4;
newInterval.e = 9;
insertNewInterval(Intervals, newInterval);
return 0;
}
Producción
1, 2 3, 10 12, 16
Complejidad de tiempo : O(nlogn)
Espacio auxiliar: O(1)
Método 3: Otro enfoque usando Stack:
Estaremos empujando pares en la pila hasta que se fusione con los intervalos o encuentre un lugar adecuado para encajarlo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <iostream>
#include <stack>
using namespace std;
// Program to merge interval
void mergeInterval2(pair<int, int> arr[],
int n, pair<int,
int> newPair)
{
// Create stack of type
// pair<int, int>
stack< pair<int, int> > stk;
// Pushing first pair
stk.push(arr[0]);
// Storing the top element
pair<int, int> top = stk.top();
// Checking is newPair.first
// is less than top.second
if (newPair.first < top.second)
{
// Pop the top element
// as it will merge with the
// previous range
stk.pop();
// Re-assigning top.first
top.first = min(top.first,
newPair.first);
// Re-assigning top.second
top.second = max(top.second,
newPair.second);
// Push the current interval
stk.push(top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.push(newPair);
}
// Iterate i from 1 to n - 1
for (int i = 1; i < n; i++)
{
// Store the top element of
// the stack stk
pair<int, int> top = stk.top();
// Checking is arr[i].first
// is less than top.second
if (arr[i].first < top.second)
{
// Pop the top element
// as it will merge with the
// previous range
stk.pop();
// Re-assigning top.first
top.first = min(top.first,
arr[i].first);
// Re-assigning top.second
top.second = max(top.second,
arr[i].second);
// Push the current interval
stk.push(top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.push(arr[i]);
}
}
// Storing the final intervals
stack< pair<int,int> > finalIntervals;
// Popping the stack elements
while (stk.empty() != true)
{
pair<int, int> ele =
stk.top();
stk.pop();
// Push ele in finalIntervals
finalIntervals.push(ele);
}
// Displaying the final result
while (finalIntervals.empty() != true)
{
pair<int, int> ele =
finalIntervals.top();
finalIntervals.pop();
cout << ele.first << ", "
<< ele.second << endl;
}
}
// Driver Code
int main()
{
pair<int, int> arr2[] = {
{ 1, 2 }, { 3, 5 }, { 6, 7 },
{ 8, 10 }, { 12, 16 }
};
pair<int, int> newPair{ 4, 9 };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
// Function Call
mergeInterval2(arr2, n2, newPair);
return 0;
}
Python3
# Python3 program for above approach # Program to merge interval def mergeInterval2(arr, n, newPair) : # Create stack of type # pair<int, int> stk = [] # Pushing first pair stk.append(arr[0]) # Storing the top element top = stk[len(stk) - 1] # Checking is newPair.first # is less than top.second if (newPair[0] < top[1]) : # Pop the top element # as it will merge with the # previous range stk.pop() # Re-assigning top.first top[0] = min(top[0], newPair[0]) # Re-assigning top.second top[1] = max(top[1], newPair[1]) # Push the current interval stk.append(top) else : # Push the new pair as it does # not intersect to first pair stk.append(newPair) # Iterate i from 1 to n - 1 for i in range(1, n) : # Store the top element of # the stack stk top = stk[len(stk) - 1] # Checking is arr[i].first # is less than top.second if (arr[i][0] < top[1]) : # Pop the top element # as it will merge with the # previous range stk.pop() # Re-assigning top.first top[0] = min(top[0], arr[i][0]) # Re-assigning top.second top[1] = max(top[1], arr[i][1]) # Push the current interval stk.append(top) else : # Push the new pair as it does # not intersect to first pair stk.append(arr[i]) # Storing the final intervals finalIntervals = [] # Popping the stack elements while (len(stk) > 0) : ele = stk[len(stk) - 1] stk.pop() # Push ele in finalIntervals finalIntervals.append(ele) # Displaying the final result while (len(finalIntervals) > 0) : ele = finalIntervals[len(finalIntervals) - 1] finalIntervals.pop() print(ele[0] , end = ", ") print(ele[1]) arr2 = [ [ 1, 2 ], [ 3, 5 ], [ 6, 7 ], [ 8, 10 ], [ 12, 16 ] ] newPair = [ 4, 9 ] n2 = len(arr2) # Function Call mergeInterval2(arr2, n2, newPair) # This code is contributed by divyesh072019
C#
// C# program for above approach
using System;
using System.Collections;
class GFG{
// Function to merge interval
static void mergeInterval2(Tuple<int, int>[] arr,
int n, Tuple<int, int> newPair)
{
// Create stack of type
// pair<int, int>
Stack stk = new Stack();
// Pushing first pair
stk.Push(arr[0]);
// Storing the top element
Tuple<int,
int> top = (Tuple<int,
int>)stk.Peek();
// Checking is newPair.first
// is less than top.second
if (newPair.Item1 < top.Item2)
{
// Pop the top element
// as it will merge with the
// previous range
stk.Pop();
// Re-assigning top.first and top.second
top = new Tuple<int, int>(Math.Min(top.Item1,
newPair.Item1),
Math.Max(top.Item2,
newPair.Item2));
// Push the current interval
stk.Push(top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.Push(newPair);
}
// Iterate i from 1 to n - 1
for(int i = 1; i < n; i++)
{
// Store the top element of
// the stack stk
Tuple<int,
int> Top = (Tuple<int,
int>)stk.Peek();
// Checking is arr[i].first
// is less than top.second
if (arr[i].Item1 < Top.Item2)
{
// Pop the top element
// as it will merge with the
// previous range
stk.Pop();
// Re-assigning top.first and top.second
Top = new Tuple<int, int>(Math.Min(Top.Item1,
arr[i].Item1),
Math.Max(Top.Item2,
arr[i].Item2));
// Push the current interval
stk.Push(Top);
}
else
{
// Push the new pair as it does
// not intersect to first pair
stk.Push(arr[i]);
}
}
// Storing the final intervals
Stack finalIntervals = new Stack();
// Popping the stack elements
while (stk.Count != 0)
{
Tuple<int,
int> ele = (Tuple<int,
int>)stk.Peek();
stk.Pop();
// Push ele in finalIntervals
finalIntervals.Push(ele);
}
// Displaying the final result
while (finalIntervals.Count != 0)
{
Tuple<int,
int> ele = (Tuple<int,
int>)finalIntervals.Peek();
finalIntervals.Pop();
Console.WriteLine(ele.Item1 + ", " + ele.Item2);
}
}
// Driver Code
static void Main()
{
Tuple<int, int>[] arr2 =
{
Tuple.Create(1, 2),
Tuple.Create(3, 5),
Tuple.Create(6, 7),
Tuple.Create(8, 10),
Tuple.Create(12, 16),
};
Tuple<int,
int> newPair = new Tuple<int,
int>(4, 9);
int n2 = arr2.Length;
// Function Call
mergeInterval2(arr2, n2, newPair);
}
}
// This code is contributed by divyeshrabadiya07
Producción
1, 2 3, 10 12, 16
Complejidad temporal: O(N)
Espacio auxiliar: O(N)