Dado un conjunto de intervalos de tiempo en cualquier orden, fusione todos los intervalos superpuestos en uno y genere el resultado que debería tener solo intervalos mutuamente excluyentes.
Ejemplo:
C++
// A C++ program for merging overlapping intervals
#include <bits/stdc++.h>
using namespace std;
// An interval has start time and end time
struct Interval {
int start, end;
};
// Compares two intervals according to their starting time.
// This is needed for sorting the intervals using library
// function std::sort(). See http://goo.gl/iGspV
bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start);
}
// The main function that takes a set of intervals, merges
// overlapping intervals and prints the result
void mergeIntervals(Interval arr[], int n)
{
// Test if the given set has at least one interval
if (n <= 0)
return;
// Create an empty stack of intervals
stack<Interval> s;
// sort the intervals in increasing order of start time
sort(arr, arr + n, compareInterval);
// push the first interval to stack
s.push(arr[0]);
// Start from the next interval and merge if necessary
for (int i = 1; i < n; i++) {
// get interval from stack top
Interval top = s.top();
// if current interval is not overlapping with stack
// top, push it to the stack
if (top.end < arr[i].start)
s.push(arr[i]);
// Otherwise update the ending time of top if ending
// of current interval is more
else if (top.end < arr[i].end) {
top.end = arr[i].end;
s.pop();
s.push(top);
}
}
// Print contents of stack
cout << "\n The Merged Intervals are: ";
while (!s.empty()) {
Interval t = s.top();
cout << "[" << t.start << "," << t.end << "] ";
s.pop();
}
return;
}
// Driver program
int main()
{
Interval arr[]
= { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
int n = sizeof(arr) / sizeof(arr[0]);
mergeIntervals(arr, n);
return 0;
}
Java
// A Java program for merging overlapping intervals
import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;
public class MergeOverlappingIntervals {
// The main function that takes a set of intervals, merges
// overlapping intervals and prints the result
public static void mergeIntervals(Interval arr[])
{
// Test if the given set has at least one interval
if (arr.length <= 0)
return;
// Create an empty stack of intervals
Stack<Interval> stack=new Stack<>();
// sort the intervals in increasing order of start time
Arrays.sort(arr,new Comparator<Interval>(){
public int compare(Interval i1,Interval i2)
{
return i1.start-i2.start;
}
});
// push the first interval to stack
stack.push(arr[0]);
// Start from the next interval and merge if necessary
for (int i = 1 ; i < arr.length; i++)
{
// get interval from stack top
Interval top = stack.peek();
// if current interval is not overlapping with stack top,
// push it to the stack
if (top.end < arr[i].start)
stack.push(arr[i]);
// Otherwise update the ending time of top if ending of current
// interval is more
else if (top.end < arr[i].end)
{
top.end = arr[i].end;
stack.pop();
stack.push(top);
}
}
// Print contents of stack
System.out.print("The Merged Intervals are: ");
while (!stack.isEmpty())
{
Interval t = stack.pop();
System.out.print("["+t.start+","+t.end+"] ");
}
}
public static void main(String args[]) {
Interval arr[]=new Interval[4];
arr[0]=new Interval(6,8);
arr[1]=new Interval(1,9);
arr[2]=new Interval(2,4);
arr[3]=new Interval(4,7);
mergeIntervals(arr);
}
}
class Interval
{
int start,end;
Interval(int start, int end)
{
this.start=start;
this.end=end;
}
}
// This code is contributed by Gaurav Tiwari
C#
// A C# program for merging overlapping intervals
using System;
using System.Collections;
using System.Collections.Generic;
public class MergeOverlappingIntervals
{
// sort the intervals in increasing order of start time
class sortHelper : IComparer
{
int IComparer.Compare(object a, object b)
{
Interval first = (Interval)a;
Interval second = (Interval)b;
if (first.start == second.start)
{
return first.end - second.end;
}
return first.start - second.start;
}
}
// The main function that takes a set of intervals, merges
// overlapping intervals and prints the result
public static void mergeIntervals(Interval []arr)
{
// Test if the given set has at least one interval
if (arr.Length <= 0)
return;
Array.Sort(arr, new sortHelper());
// Create an empty stack of intervals
Stack stack = new Stack();
// Push the first interval to stack
stack.Push(arr[0]);
// Start from the next interval and merge if necessary
for (int i = 1 ; i < arr.Length; i++)
{
// get interval from stack top
Interval top = (Interval)stack.Peek();
// if current interval is not overlapping with stack top,
// Push it to the stack
if (top.end < arr[i].start)
stack.Push(arr[i]);
// Otherwise update the ending time of top if ending of current
// interval is more
else if (top.end < arr[i].end)
{
top.end = arr[i].end;
stack.Pop();
stack.Push(top);
}
}
// Print contents of stack
Console.Write("The Merged Intervals are: ");
while (stack.Count != 0)
{
Interval t = (Interval)stack.Pop();
Console.Write("[" + t.start + "," + t.end + "] ");
}
}
// Driver code
public static void Main()
{
Interval []arr = new Interval[4];
arr[0] = new Interval(6, 8);
arr[1] = new Interval(1, 9);
arr[2] = new Interval(2, 4);
arr[3] = new Interval(4, 7);
mergeIntervals(arr);
}
}
public class Interval
{
public int start,end;
public Interval(int start, int end)
{
this.start = start;
this.end = end;
}
}
// This code is contributed by rutvik_56.
Python3
def mergeIntervals(intervals):
# Sort the array on the basis of start values of intervals.
intervals.sort()
stack = []
# insert first interval into stack
stack.append(intervals[0])
for i in intervals[1:]:
# Check for overlapping interval,
# if interval overlap
if stack[-1][0] <= i[0] <= stack[-1][-1]:
stack[-1][-1] = max(stack[-1][-1], i[-1])
else:
stack.append(i)
print("The Merged Intervals are :", end=" ")
for i in range(len(stack)):
print(stack[i], end=" ")
arr = [[6, 8], [1, 9], [2, 4], [4, 7]]
mergeIntervals(arr)
C++
// C++ program to merge overlapping Intervals in
// O(n Log n) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
// An Interval
struct Interval {
int s, e;
};
// Function used in sort
bool mycomp(Interval a, Interval b) { return a.s < b.s; }
void mergeIntervals(Interval arr[], int n)
{
// Sort Intervals in increasing order of
// start time
sort(arr, arr + n, mycomp);
int index = 0; // Stores index of last element
// in output array (modified arr[])
// Traverse all input Intervals
for (int i = 1; i < n; i++) {
// If this is not first Interval and overlaps
// with the previous one
if (arr[index].e >= arr[i].s) {
// Merge previous and current Intervals
arr[index].e = max(arr[index].e, arr[i].e);
}
else {
index++;
arr[index] = arr[i];
}
}
// Now arr[0..index-1] stores the merged Intervals
cout << "\n The Merged Intervals are: ";
for (int i = 0; i <= index; i++)
cout << "[" << arr[i].s << ", " << arr[i].e << "] ";
}
// Driver program
int main()
{
Interval arr[]
= { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
int n = sizeof(arr) / sizeof(arr[0]);
mergeIntervals(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to merge overlapping Intervals in
// O(n Log n) time and O(1) extra space.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// An Interval
typedef struct Interval {
int s, e;
} Interval;
// Function used in sort
int mycomp(const void* a, const void* b)
{
Interval* data_1 = (Interval*)a;
Interval* data_2 = (Interval*)b;
return (data_1->s - data_2->s);
}
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
void mergeIntervals(Interval arr[], int n)
{
// Sort Intervals in increasing order of
// start time
qsort(arr, n, sizeof(Interval), mycomp);
int index = 0; // Stores index of last element
// in output array (modified arr[])
// Traverse all input Intervals
for (int i = 1; i < n; i++) {
// If this is not first Interval and overlaps
// with the previous one
if (arr[index].e >= arr[i].s) {
// Merge previous and current Intervals
arr[index].e = max(arr[index].e, arr[i].e);
}
else {
index++;
arr[index] = arr[i];
}
}
// Now arr[0..index-1] stores the merged Intervals
printf("\n The Merged Intervals are: ");
for (int i = 0; i <= index; i++)
printf("[%d, %d]", arr[i].s, arr[i].e);
}
// Driver program
int main()
{
Interval arr[]
= { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } };
int n = sizeof(arr) / sizeof(arr[0]);
mergeIntervals(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to merge overlapping Intervals in
// O(n Log n) time and O(1) extra space
import java.util.Arrays;
import java.util.Comparator;
// An Interval
class Interval
{
int start,end;
Interval(int start, int end)
{
this.start=start;
this.end=end;
}
}
public class MergeOverlappingIntervals {
// Function that takes a set of intervals, merges
// overlapping intervals and prints the result
public static void mergeIntervals(Interval arr[])
{
// Sort Intervals in increasing order of
// start time
Arrays.sort(arr,new Comparator<Interval>(){
public int compare(Interval i1,Interval i2)
{
return i1.start - i2.start;
}
});
int index = 0; // Stores index of last element
// in output array (modified arr[])
// Traverse all input Intervals
for (int i=1; i<arr.length; i++)
{
// If this is not first Interval and overlaps
// with the previous one
if (arr[index].end >= arr[i].start)
{
// Merge previous and current Intervals
arr[index].end = Math.max(arr[index].end, arr[i].end);
}
else {
index++;
arr[index] = arr[i];
}
}
// Now arr[0..index-1] stores the merged Intervals
System.out.print("The Merged Intervals are: ");
for (int i = 0; i <= index; i++)
{
System.out.print("[" + arr[i].start + ","
+ arr[i].end + "]");
}
}
// Driver Code
public static void main(String args[]) {
Interval arr[]=new Interval[4];
arr[0]=new Interval(6,8);
arr[1]=new Interval(1,9);
arr[2]=new Interval(2,4);
arr[3]=new Interval(4,7);
mergeIntervals(arr);
}
}
// This code is contributed by Gaurav Tiwari
// This code was fixed by Subham Mukhopadhyay
Python3
# Python program to merge overlapping Intervals in
# O(n Log n) time and O(1) extra space
def mergeIntervals(arr):
# Sorting based on the increasing order
# of the start intervals
arr.sort(key=lambda x: x[0])
# Stores index of last element
# in output array (modified arr[])
index = 0
# Traverse all input Intervals starting from
# second interval
for i in range(1, len(arr)):
# If this is not first Interval and overlaps
# with the previous one, Merge previous and
# current Intervals
if (arr[index][1] >= arr[i][0]):
arr[index][1] = max(arr[index][1], arr[i][1])
else:
index = index + 1
arr[index] = arr[i]
print("The Merged Intervals are :", end=" ")
for i in range(index+1):
print(arr[i], end=" ")
# Driver code
arr = [[6, 8], [1, 9], [2, 4], [4, 7]]
mergeIntervals(arr)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA