Рубрики

Объединить перекрывающиеся интервалы

Учитывая набор временных интервалов в любом порядке, объедините все перекрывающиеся интервалы в один и выведите результат, который должен иметь только взаимоисключающие интервалы. Пусть интервалы представляются в виде пар целых чисел для простоты.
Например, пусть заданным набором интервалов будет {{1,3}, {2,4}, {5,7}, {6,8}}. Интервалы {1,3} и {2,4} перекрываются друг с другом, поэтому они должны быть объединены и стать {1, 4}. Аналогичным образом {5, 7} и {6, 8} должны быть объединены и стать {5, 8}

Напишите функцию, которая производит набор объединенных интервалов для данного набора интервалов.

Простой подход состоит в том, чтобы начать с первого интервала и сравнить его со всеми другими интервалами для перекрытия, если он перекрывается с любым другим интервалом, затем удалить другой интервал из списка и объединить другой в первый интервал. Повторите те же шаги для оставшихся интервалов после первого. Этот подход не может быть реализован за время, превышающее O (n ^ 2).

Эффективный подход — сначала отсортировать интервалы по времени запуска. Получив отсортированные интервалы, мы можем объединить все интервалы в линейный обход. Идея состоит в том, что в отсортированном массиве интервалов, если интервал [i] не перекрывается с интервалом [i-1], то интервал [i + 1] не может перекрываться с интервалом [i-1], поскольку время начала интервала [i] +1] должен быть больше или равен интервалу [i]. Ниже приведен подробный пошаговый алгоритм.

1. Sort the intervals based on increasing order of 
    starting time.
2. Push the first interval on to a stack.
3. For each interval do the following
   a. If the current interval does not overlap with the stack 
       top, push it.
   b. If the current interval overlaps with stack top and ending
       time of current interval is more than that of stack top, 
       update stack top with the ending  time of current interval.
4. At the end stack contains the merged intervals. 

Ниже приведена реализация вышеуказанного подхода.

C ++

// Программа на C ++ для объединения перекрывающихся интервалов
#include<bits/stdc++.h>

using namespace std;

  
// Интервал имеет время начала и время окончания

struct Interval

{

    int start, end;

};

  
// Сравнивает два интервала по времени их начала.
// Это необходимо для сортировки интервалов с использованием библиотеки
// функция std :: sort (). Смотрите http://goo.gl/iGspV

bool compareInterval(Interval i1, Interval i2)

{

    return (i1.start < i2.start);

}

  
// Основная функция, которая принимает набор интервалов, объединяет
// перекрывающиеся интервалы и выводит результат

void mergeIntervals(Interval arr[], int n)

{

    // Проверяем, имеет ли данный набор хотя бы один интервал

    if (n <= 0)

        return;

  

    // Создать пустой стек интервалов

    stack<Interval> s;

  

    // сортируем интервалы в порядке возрастания времени начала

    sort(arr, arr+n, compareInterval);

  

    // вставляем первый интервал в стек

    s.push(arr[0]);

  

    // Начать со следующего интервала и объединить при необходимости

    for (int i = 1 ; i < n; i++)

    {

        // получаем интервал от вершины стека

        Interval top = s.top();

  

        // если текущий интервал не перекрывается с вершиной стека,

        // положить его в стек

        if (top.end < arr[i].start)

            s.push(arr[i]);

  

        // В противном случае обновляем время окончания вершины, если конец текущего

        // интервал больше

        else if (top.end < arr[i].end)

        {

            top.end = arr[i].end;

            s.pop();

            s.push(top);

        }

    }

  

    // Распечатать содержимое стека

    cout << "\n The Merged Intervals are: ";

    while (!s.empty())

    {

        Interval t = s.top();

        cout << "[" << t.start << "," << t.end << "] ";

        s.pop();

    }

    return;

}

  
// Драйвер программы

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-программа для объединения перекрывающихся интервалов

import java.util.Arrays;

import java.util.Comparator;

import java.util.Stack;

public class MergeOverlappingIntervals {

  

    // Основная функция, которая принимает набор интервалов, объединяет

    // перекрывающиеся интервалы и выводит результат

    public static void mergeIntervals(Interval arr[]) 

    

        // Проверяем, имеет ли данный набор хотя бы один интервал

        if (arr.length <= 0

            return

    

        // Создать пустой стек интервалов

        Stack<Interval> stack=new Stack<>();

    

        // сортируем интервалы в порядке возрастания времени начала

        Arrays.sort(arr,new Comparator<Interval>(){

            public int compare(Interval i1,Interval i2)

            {

                return i1.start-i2.start;

            }

        });

    

        // вставляем первый интервал в стек

        stack.push(arr[0]); 

    

        // Начать со следующего интервала и объединить при необходимости

        for (int i = 1 ; i < arr.length; i++) 

        

            // получаем интервал от вершины стека

            Interval top = stack.peek(); 

    

            // если текущий интервал не перекрывается с вершиной стека,

            // положить его в стек

            if (top.end < arr[i].start) 

                stack.push(arr[i]); 

    

            // В противном случае обновляем время окончания вершины, если конец текущего

            // интервал больше

            else if (top.end < arr[i].end) 

            

                top.end = arr[i].end; 

                stack.pop(); 

                stack.push(top); 

            

        

    

        // Распечатать содержимое стека

        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;

    }

}
// Этот код предоставлен Гауравом Тивари


Выход:

 The Merged Intervals are: [1,9] 

Временная сложность метода O (nLogn), которая предназначена для сортировки. После сортировки массива интервалов слияние занимает линейное время.

AO (n Log n) и O (1) Решение для дополнительного пространства
Приведенное выше решение требует O (n) дополнительного пространства для стека. Мы можем избежать использования дополнительного пространства, выполняя операции слияния на месте. Ниже приведены подробные шаги.

1) Sort all intervals in decreasing order of start time.
2) Traverse sorted intervals starting from first interval, 
   do following for every interval.
      a) If current interval is not first interval and it 
         overlaps with previous interval, then merge it with
         previous interval. Keep doing it while the interval
         overlaps with the previous one.         
      b) Else add current interval to output list of intervals.

Обратите внимание, что если интервалы сортируются по убыванию порядка времени начала, мы можем быстро проверить, перекрываются ли интервалы или нет, сравнивая время начала предыдущего интервала с временем окончания текущего интервала.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для объединения перекрывающихся интервалов в
// O (n Log n) время и O (1) дополнительное пространство.
#include<bits/stdc++.h> 

using namespace std; 

  
// Интервал

struct Interval 

    int s, e; 

}; 

  
// Функция, используемая в сортировке

bool mycomp(Interval a, Interval b) 

{ return a.s < b.s; } 

  

void mergeIntervals(Interval arr[], int n) 

    // Сортировка интервалов в порядке возрастания

    // начальное время

    sort(arr, arr+n, mycomp); 

  

    int index = 0; // Сохраняет индекс последнего элемента

    // в выходном массиве (модифицированный arr [])

  

    // Обход всех входных интервалов

    for (int i=1; i<n; i++) 

    

        // Если это не первый Интервал и перекрытия

        // с предыдущим

        if (arr[index].e >=  arr[i].s) 

        

               // Объединяем предыдущий и текущий интервалы

            arr[index].e = max(arr[index].e, arr[i].e); 

            arr[index].s = min(arr[index].s, arr[i].s); 

        

        else {

            arr[index] = arr[i]; 

            index++;

        }    

    

  

    // Теперь arr [0..index-1] сохраняет объединенные интервалы

    cout << "\n The Merged Intervals are: "

    for (int i = 0; i <= index; i++) 

        cout << "[" << arr[i].s << ", " << arr[i].e << "] "

  
// Драйвер программы

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-программа для объединения перекрывающихся интервалов в
// O (n Log n) время и O (1) дополнительное пространство

  

import java.util.Arrays;

import java.util.Comparator;

  
// Интервал

class Interval

{

    int start,end;

      

    Interval(int start, int end)

    {

        this.start=start;

        this.end=end;

    }

}

  

public class MergeOverlappingIntervals {

      

    // Функция, которая принимает набор интервалов, объединяет

    // перекрывающиеся интервалы и выводит результат

    public static void mergeIntervals(Interval arr[]) 

    

        // Сортировка интервалов в порядке убывания

        // начальное время

        Arrays.sort(arr,new Comparator<Interval>(){

            public int compare(Interval i1,Interval i2)

            {

                return i2.start - i1.start;

            }

        });

    

        int index = 0; // Сохраняет индекс последнего элемента

        // в выходном массиве (модифицированный arr [])

    

        // Обход всех входных интервалов

        for (int i=1; i<arr.length; i++) 

        

            // Если это не первый Интервал и перекрытия

            // с предыдущим

            if (arr[index].end >=  arr[i].start) 

            

                   // Объединяем предыдущий и текущий интервалы

                arr[index].end = Math.max(arr[index].end, arr[i].end); 

                arr[index].start = Math.min(arr[index].start, arr[i].start); 

            

            else {

                arr[index] = arr[i]; 

                index++;

            }    

        }

          

        // Теперь arr [0..index-1] сохраняет объединенные интервалы

        System.out.print("The Merged Intervals are: ");

        for (int i = 0; i <= index; i++) 

        {

            System.out.print("[" + arr[i].start + "," 

                                        + arr[i].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);

    }

}

  
// Этот код предоставлен Гауравом Тивари

python3

# Python3 программа для объединения перекрывающихся интервалов
# в O (n Log n) время и O (1) дополнительное пространство

def mergeIntervals(arr):

          

        # Сортировка по возрастанию

        Количество стартовых интервалов

        arr.sort(key = lambda x: x[0]) 

          

        # массив для хранения объединенных интервалов

        m = []

        s = -10000

        max = -100000

        for i in range(len(arr)):

            a = arr[i]

            if a[0] > max:

                if i != 0:

                    m.append([s,max])

                max = a[1]

                s = a[0]

            else:

                if a[1] >= max:

                    max = a[1]

          

        # 'max' значение дает последнюю точку

        # этот конкретный интервал

        # 's' дает начальную точку этого интервала

        Массив # 'm' содержит список всех объединенных интервалов

  

        if max != -100000 and [s, max] not in m:

            m.append([s, max])

        print("The Merged Intervals are :", end = " ")

        for i in range(len(m)):

            print(m[i], end = " ")

  
# Код драйвера

arr = [[6, 8], [1, 9], [2, 4], [4, 7]]

mergeIntervals(arr)

  
# Этот код добавлен
# от triumalai srinivasan


Выход:

 The Merged Intervals are: [1,9] 

Спасибо Гаураву Ахирвару за то, что он предложил этот метод.

Эта статья составлена Рави Чандрой Энаганти. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Объединить перекрывающиеся интервалы

0.00 (0%) 0 votes