Dado N conjunto de intervalos de tiempo, la tarea es encontrar los intervalos que no se superponen con el conjunto de intervalos dado.
Ejemplos:
Entrada: intervalo arr[] = { {1, 3}, {2, 4}, {3, 5}, {7, 9} } Salida: [5, 7] Explicación: El único intervalo que
no
se
superpone
con los otros intervalos son [5, 7].
Entrada: intervalo arr[] = { {1, 3}, {9, 12}, {2, 4}, {6, 8} } Salida: [4, 6] [8, 9]
Explicación
:
Hay
dos
intervalos que no se superponen con otros intervalos son [4, 6], [8, 9].
Enfoque: La idea es ordenar los intervalos de tiempo dados según la hora de inicio y si los intervalos consecutivos no se superponen, la diferencia entre ellos es el intervalo libre.
A continuación se muestran los pasos:
- Ordene el conjunto dado de intervalos según la hora de inicio.
- Atraviese todo el conjunto de intervalos y compruebe si los intervalos consecutivos se superponen o no .
- Si los intervalos (por ejemplo, el intervalo a y el intervalo b ) no se superponen, entonces el conjunto de pares formado por [a.end, b.start] es el intervalo que no se superpone.
- Si los intervalos se superponen, compruebe los siguientes intervalos consecutivos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
// interval with start time & end time
struct interval {
int start, end;
};
// Comparator function to sort the given
// interval according to time
bool compareinterval(interval i1, interval i2)
{
return (i1.start < i2.start);
}
// Function that find the free interval
void findFreeinterval(interval arr[], int N)
{
// If there are no set of interval
if (N <= 0) {
return;
}
// To store the set of free interval
vector<pair<int, int> > P;
// Sort the given interval according
// starting time
sort(arr, arr + N, compareinterval);
// Iterate over all the interval
for (int i = 1; i < N; i++) {
// Previous interval end
int prevEnd = arr[i - 1].end;
// Current interval start
int currStart = arr[i].start;
// If ending index of previous
// is less than starting index
// of current, then it is free
// interval
if (prevEnd < currStart) {
P.push_back({ prevEnd,
currStart });
}
}
// Print the free interval
for (auto& it : P) {
cout << "[" << it.first << ", "
<< it.second << "]" << endl;
}
}
// Driver Code
int main()
{
// Given set of interval
interval arr[] = { { 1, 3 },
{ 2, 4 },
{ 3, 5 },
{ 7, 9 } };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
findFreeinterval(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Interval with start time & end time
static class Interval
{
int start, end;
Interval(int start, int end)
{
this.start = start;
this.end = end;
}
}
// Function that find the free interval
static void findFreeinterval(int[][] arr, int N)
{
// If there are no set of interval
if (N <= 0)
{
return;
}
// To store the set of free interval
ArrayList<Interval> p = new ArrayList<>();
// Sort the given interval according
// starting time
Arrays.sort(arr, new Comparator<int[]>()
{
public int compare(int[] a, int[] b)
{
return a[0] - b[0];
}
});
// Iterate over all the interval
for (int i = 1; i < N; i++)
{
// Previous interval end
int prevEnd = arr[i - 1][1];
// Current interval start
int currStart = arr[i][0];
// If ending index of previous
// is less than starting index
// of current, then it is free
// interval
if (prevEnd < currStart)
{
Interval interval = new Interval(prevEnd,
currStart);
p.add(interval);
}
}
// Print the free interval
for (int i = 0; i < p.size(); i++)
{
System.out.println("[" + p.get(i).start +
", " + p.get(i).end + "]");
}
}
// Driver code
public static void main(String[] args)
{
// Given set of interval
int[][] arr = { { 1, 3 },
{ 2, 4 },
{ 3, 5 },
{ 7, 9 } };
int N = arr.length;
// Function Call
findFreeinterval(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach def findFreeinterval(arr, N): # If there are no set of interval if N < 1: return # To store the set of free interval P = [] # Sort the given interval according # Starting time arr.sort(key = lambda a:a[0]) # Iterate over all the interval for i in range(1, N): # Previous interval end prevEnd = arr[i - 1][1] # Current interval start currStart = arr[i][0] # If Previous Interval is less # than current Interval then we # store that answer if prevEnd < currStart: P.append([prevEnd, currStart]) # Print the intervals for i in P: print(i) # Driver code if __name__ == "__main__": # Given List of intervals arr = [ [ 1, 3 ], [ 2, 4 ], [ 3, 5 ], [ 7, 9 ] ] N = len(arr) # Function call findFreeinterval(arr, N) # This code is contributed by Tokir Manva
Javascript
<script>
// Javascript program for the above approach
// Function that find the free interval
function findFreeinterval(arr, N)
{
// If there are no set of interval
if (N <= 0) {
return;
}
// To store the set of free interval
var P = [];
// Sort the given interval according
// starting time
arr.sort((a,b) => a[0]-b[0])
// Iterate over all the interval
for (var i = 1; i < N; i++) {
// Previous interval end
var prevEnd = arr[i - 1][1];
// Current interval start
var currStart = arr[i][0];
// If ending index of previous
// is less than starting index
// of current, then it is free
// interval
if (prevEnd < currStart) {
P.push([prevEnd,
currStart]);
}
}
// Print the free interval
P.forEach(it => {
document.write( "[" + it[0] + ", "
+ it[1] + "]");
});
}
// Driver Code
// Given set of interval
var arr = [ [ 1, 3 ],
[ 2, 4 ],
[ 3, 5 ],
[ 7, 9 ] ];
var N = arr.length;
// Function Call
findFreeinterval(arr, N);
// This code is contributed by noob2000.
</script>
Producción:
[5, 7]
Complejidad de tiempo: O(N*log N) , donde N es el número del conjunto de intervalos.
Espacio Auxiliar: O(N)