Рубрики

Учитывая n встреч, найдите все конфликтующие встречи

Учитывая n встреч, найдите все конфликтующие встречи.

Примеры:

Input: appointments[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}
Output: Following are conflicting intervals
[3,7] Conflicts with [1,5]
[2,6] Conflicts with [1,5]
[5,6] Conflicts with [3,7]
[4,100] Conflicts with [1,5]

Встреча конфликтует, если она конфликтует с любым из предыдущих встреч в массиве.

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.

Простое решение состоит в том, чтобы один за другим обрабатывать все встречи от второго до последнего. Для каждого назначения i проверьте, не конфликтует ли оно с i-1, i-2,… 0. Временная сложность этого метода составляет O (n 2 ).

Мы можем использовать Interval Tree для решения этой проблемы за O (nLogn) время. Ниже приводится подробный алгоритм.

1) Create an Interval Tree, initially with the first appointment.
2) Do following for all other appointments starting from the second one.
   a) Check if the current appointment conflicts with any of the existing 
     appointments in Interval Tree.  If conflicts, then print the current
     appointment.  This step can be done O(Logn) time.
   b) Insert the current appointment in Interval Tree. This step also can
      be done O(Logn) time.

Ниже приводится реализация вышеуказанной идеи на C ++.

// C ++ программа для печати всех конфликтующих встреч в
// данный набор встреч
#include <iostream>

using namespace std;

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

struct Interval

{

    int low, high;

};

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

struct ITNode

{

    Interval *i;  // 'i' также может быть нормальной переменной

    int max;

    ITNode *left, *right;

};

  
// Вспомогательная функция для создания нового узла дерева интервального поиска
ITNode * newNode(Interval i)
{

    ITNode *temp = new ITNode;

    temp->i = new Interval(i);

    temp->max = i.high;

    temp->left = temp->right = NULL;

};

  
// Утилита для вставки нового дерева поиска по интервалам
// Узел Это похоже на вставку BST. Здесь низкое значение
// интервала используется для поддержания свойства BST
ITNode *insert(ITNode *root, Interval i)
{

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

    if (root == NULL)

        return newNode(i);

  

    // Получить низкое значение интервала в корне

    int l = root->i->low;

  

    // Если нижнее значение root меньше, то новый интервал

    // идет в левое поддерево

    if (i.low < l)

        root->left = insert(root->left, i);

  

    // Иначе, новый узел переходит в правое поддерево.

    else

        root->right = insert(root->right, i);

  

    // Обновляем максимальное значение этого предка, если это необходимо

    if (root->max < i.high)

        root->max = i.high;

  

    return root;

}

  
// Утилита для проверки перекрытия заданных двух интервалов

bool doOVerlap(Interval i1, Interval i2)

{

    if (i1.low < i2.high && i2.low < i1.high)

        return true;

    return false;

}

  
// Основная функция, которая ищет заданный интервал i
// в заданном дереве интервалов.
Interval *overlapSearch(ITNode *root, Interval i)
{

    // Базовый случай, дерево пусто

    if (root == NULL) return NULL;

  

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

    if (doOVerlap(*(root->i), i))

        return root->i;

  

    // Если присутствует левый потомок root и максимум левого потомка

    // больше или равен заданному интервалу, тогда я могу

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

    if (root->left != NULL && root->left->max >= i.low)

        return overlapSearch(root->left, i);

  

    // Остальные интервалы могут перекрываться только с правым поддеревом

    return overlapSearch(root->right, i);

}

  
// Эта функция печатает все конфликтующие встречи в данном
// массив точек.

void printConflicting(Interval appt[], int n)

{

     // Создать пустое дерево поиска по интервалам, добавить сначала

     // деловое свидание, встреча

     ITNode *root = NULL;

     root = insert(root, appt[0]);

  

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

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

     {

         // Если текущая встреча вступает в конфликт с любым из

         // существующие интервалы, распечатать его

         Interval *res = overlapSearch(root, appt[i]);

         if (res != NULL)

            cout << "[" << appt[i].low << "," << appt[i].high

                 << "] Conflicts with [" << res->low << ","

                 << res->high << "]\n";

  

         // Вставить это назначение

         root = insert(root, appt[i]);

     }

}

  

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Давайте создадим дерево интервалов, показанное на рисунке выше

    Interval appt[] = { {1, 5}, {3, 7}, {2, 6}, {10, 15},

                        {5, 6}, {4, 100}};

    int n = sizeof(appt)/sizeof(appt[0]);

    cout << "Following are conflicting intervals\n";

    printConflicting(appt, n);

    return 0;

}

Выход:

Following are conflicting intervals
[3,7] Conflicts with [1,5]
[2,6] Conflicts with [1,5]
[5,6] Conflicts with [3,7]
[4,100] Conflicts with [1,5]

Обратите внимание, что в приведенной выше реализации используются простые операции вставки в двоичное дерево поиска. Следовательно, временная сложность вышеописанной реализации больше, чем O (nLogn). Мы можем использовать методы балансировки Red-Black Tree или AVL Tree , чтобы сделать вышеописанную реализацию O (nLogn).

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

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

Учитывая n встреч, найдите все конфликтующие встречи

0.00 (0%) 0 votes