Dadas n citas, busque todas las citas en conflicto.
Ejemplos:
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]
Una cita es conflictiva si entra en conflicto con alguna de las citas anteriores de la array.
Recomendamos encarecidamente minimizar el navegador y probarlo usted mismo primero.
Una solución simple es procesar una por una todas las citas desde la segunda cita hasta la última. Para cada cita i, compruebe si entra en conflicto con i-1, i-2, … 0. La complejidad temporal de este método es O(n 2 ).
Podemos usar Interval Tree para resolver este problema en tiempo O(nLogn). A continuación se muestra un algoritmo detallado.
- Cree un árbol de intervalos, inicialmente con la primera cita.
- Haga lo siguiente para todas las demás citas a partir de la segunda.
- Compruebe si la cita actual entra en conflicto con alguna de las citas existentes en el árbol de intervalos. Si hay conflicto, imprima la cita actual. Este paso se puede hacer O (Iniciar sesión) tiempo.
- Inserte la cita actual en el árbol de intervalos. Este paso también se puede realizar O(Log) time.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print all conflicting appointments in a // given set of appointments #include <bits/stdc++.h> using namespace std; // Structure to represent an interval struct Interval { int low, high; }; // Structure to represent a node in Interval Search Tree struct ITNode { Interval *i; // 'i' could also be a normal variable int max; ITNode *left, *right; }; // A utility function to create a new Interval Search Tree Node ITNode * newNode(Interval i) { ITNode *temp = new ITNode; temp->i = new Interval(i); temp->max = i.high; temp->left = temp->right = NULL; return temp; }; // A utility function to insert a new Interval Search Tree // Node. This is similar to BST Insert. Here the low value // of interval is used tomaintain BST property ITNode *insert(ITNode *root, Interval i) { // Base case: Tree is empty, new node becomes root if (root == NULL) return newNode(i); // Get low value of interval at root int l = root->i->low; // If root's low value is smaller, then new interval // goes to left subtree if (i.low < l) root->left = insert(root->left, i); // Else, new node goes to right subtree. else root->right = insert(root->right, i); // Update the max value of this ancestor if needed if (root->max < i.high) root->max = i.high; return root; } // A utility function to check if given two intervals overlap bool doOVerlap(Interval i1, Interval i2) { if (i1.low < i2.high && i2.low < i1.high) return true; return false; } // The main function that searches a given interval i // in a given Interval Tree. Interval *overlapSearch(ITNode *root, Interval i) { // Base Case, tree is empty if (root == NULL) return NULL; // If given interval overlaps with root if (doOVerlap(*(root->i), i)) return root->i; // If left child of root is present and max of left child // is greater than or equal to given interval, then i may // overlap with an interval is left subtree if (root->left != NULL && root->left->max >= i.low) return overlapSearch(root->left, i); // Else interval can only overlap with right subtree return overlapSearch(root->right, i); } // This function prints all conflicting appointments in a given // array of appointments. void printConflicting(Interval appt[], int n) { // Create an empty Interval Search Tree, add first // appointment ITNode *root = NULL; root = insert(root, appt[0]); // Process rest of the intervals for (int i=1; i<n; i++) { // If current appointment conflicts with any of the // existing intervals, print it Interval *res = overlapSearch(root, appt[i]); if (res != NULL) cout << "[" << appt[i].low << "," << appt[i].high << "] Conflicts with [" << res->low << "," << res->high << "]\n"; // Insert this appointment root = insert(root, appt[i]); } } // Driver program to test above functions int main() { // Let us create interval tree shown in above figure 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; }
Java
// Java program to print all conflicting // appointments in a given set of appointments class GfG{ // Structure to represent an interval static class Interval { int low, high; } static class ITNode { // 'i' could also be a normal variable Interval i; int max; ITNode left, right; } // A utility function to create a new node static Interval newNode(int l, int h) { Interval temp = new Interval(); temp.low = l; temp.high = h; return temp; } // A utility function to create a new node static ITNode newNode(Interval i) { ITNode temp = new ITNode(); temp.i = i; temp.max = i.high; temp.left = temp.right = null; return temp; } // A utility function to insert a new // Interval Search Tree Node. This is // similar to BST Insert. Here the // low value of interval is used to // maintain BST property static ITNode insert(ITNode root, Interval i) { // Base case: Tree is empty, // new node becomes root if (root == null) return newNode(i); // Get low value of interval at root int l = root.i.low; // If root's low value is smaller, // then new interval goes to left subtree if (i.low < l) root.left = insert(root.left, i); // Else, new node goes to right subtree. else root.right = insert(root.right, i); // Update the max value of this // ancestor if needed if (root.max < i.high) root.max = i.high; return root; } // A utility function to check if given // two intervals overlap static boolean doOVerlap(Interval i1, Interval i2) { if (i1.low < i2.high && i2.low < i1.high) return true; return false; } // The main function that searches a given // interval i in a given Interval Tree. static Interval overlapSearch(ITNode root, Interval i) { // Base Case, tree is empty if (root == null) return null; // If given interval overlaps with root if (doOVerlap(root.i, i)) return root.i; // If left child of root is present // and max of left child is greater // than or equal to given interval, // then i may overlap with an interval // is left subtree if (root.left != null && root.left.max >= i.low) return overlapSearch(root.left, i); // Else interval can only // overlap with right subtree return overlapSearch(root.right, i); } // This function prints all conflicting // appointments in a given array of appointments. static void printConflicting(Interval appt[], int n) { // Create an empty Interval Search // Tree, add first appointment ITNode root = null; root = insert(root, appt[0]); // Process rest of the intervals for(int i = 1; i < n; i++) { // If current appointment conflicts // with any of the existing intervals, // print it Interval res = overlapSearch(root, appt[i]); if (res != null) System.out.print("[" + appt[i].low + "," + appt[i].high + "] Conflicts with [" + res.low + "," + res.high + "]\n"); // Insert this appointment root = insert(root, appt[i]); } } // Driver code public static void main(String[] args) { Interval appt[] = new Interval[6]; appt[0] = newNode(1, 5); appt[1] = newNode(3, 7); appt[2] = newNode(2, 6); appt[3] = newNode(10, 15); appt[4] = newNode(5, 6); appt[5] = newNode(4, 100); int n = appt.length; System.out.print( "Following are conflicting intervals\n"); printConflicting(appt, n); } } // This code is contributed by tushar_bansal
Python3
# Python3 program to print all conflicting # appointments in a given set of appointments # Structure to represent an interval class Interval: def __init__(self): self.low = None self.high = None # Structure to represent a node # in Interval Search Tree class ITNode: def __init__(self): self.max = None self.i = None self.left = None self.right = None def newNode(j): #print(j) temp = ITNode() temp.i = j temp.max = j[1] return temp # A utility function to check if # given two intervals overlap def doOVerlap(i1, i2): if (i1[0] < i2[1] and i2[0] < i1[1]): return True return False # Function to create a new node def insert(node, data): global succ # If the tree is empty, return a new node root = node if (node == None): return newNode(data) # If key is smaller than root's key, go to left # subtree and set successor as current node # print(node) if (data[0] < node.i[0]): # print(node) root.left = insert(node.left, data) # Go to right subtree else: root.right = insert(node.right, data) if root.max < data[1]: root.max = data[1] return root # The main function that searches a given # interval i in a given Interval Tree. def overlapSearch(root, i): # Base Case, tree is empty if (root == None): return None # If given interval overlaps with root if (doOVerlap(root.i, i)): return root.i # If left child of root is present and # max of left child is greater than or # equal to given interval, then i may # overlap with an interval is left subtree if (root.left != None and root.left.max >= i[0]): return overlapSearch(root.left, i) # Else interval can only overlap # with right subtree return overlapSearch(root.right, i) # This function prints all conflicting # appointments in a given array of # appointments. def printConflicting(appt, n): # Create an empty Interval Search Tree, # add first appointment root = None root = insert(root, appt[0]) # Process rest of the intervals for i in range(1, n): # If current appointment conflicts # with any of the existing intervals, # print it res = overlapSearch(root, appt[i]) if (res != None): print("[", appt[i][0], ",", appt[i][1], "] Conflicts with [", res[0], ",", res[1], "]") # Insert this appointment root = insert(root, appt[i]) # Driver code if __name__ == '__main__': # Let us create interval tree # shown in above figure appt = [ [ 1, 5 ], [ 3, 7 ], [ 2, 6 ], [ 10, 15 ], [ 5, 6 ], [ 4, 100 ] ] n = len(appt) print("Following are conflicting intervals") printConflicting(appt, n) # This code is contributed by mohit kumar 29
C#
// C# program to print all conflicting // appointments in a given set of appointments using System; public class GfG { // Structure to represent an interval public class Interval { public int low, high; } public class ITNode { // 'i' could also be a normal variable public Interval i; public int max; public ITNode left, right; } // A utility function to create a new node static Interval newNode(int l, int h) { Interval temp = new Interval(); temp.low = l; temp.high = h; return temp; } // A utility function to create a new node static ITNode newNode(Interval i) { ITNode temp = new ITNode(); temp.i = i; temp.max = i.high; temp.left = temp.right = null; return temp; } // A utility function to insert a new // Interval Search Tree Node. This is // similar to BST Insert. Here the // low value of interval is used to // maintain BST property static ITNode insert(ITNode root, Interval i) { // Base case: Tree is empty, // new node becomes root if (root == null) return newNode(i); // Get low value of interval at root int l = root.i.low; // If root's low value is smaller, // then new interval goes to left subtree if (i.low < l) root.left = insert(root.left, i); // Else, new node goes to right subtree. else root.right = insert(root.right, i); // Update the max value of this // ancestor if needed if (root.max < i.high) root.max = i.high; return root; } // A utility function to check if given // two intervals overlap static bool doOVerlap(Interval i1, Interval i2) { if (i1.low < i2.high && i2.low < i1.high) return true; return false; } // The main function that searches a given // interval i in a given Interval Tree. static Interval overlapSearch(ITNode root, Interval i) { // Base Case, tree is empty if (root == null) return null; // If given interval overlaps with root if (doOVerlap(root.i, i)) return root.i; // If left child of root is present // and max of left child is greater // than or equal to given interval, // then i may overlap with an interval // is left subtree if (root.left != null && root.left.max >= i.low) return overlapSearch(root.left, i); // Else interval can only // overlap with right subtree return overlapSearch(root.right, i); } // This function prints all conflicting // appointments in a given array of appointments. static void printConflicting(Interval []appt, int n) { // Create an empty Interval Search // Tree, add first appointment ITNode root = null; root = insert(root, appt[0]); // Process rest of the intervals for(int i = 1; i < n; i++) { // If current appointment conflicts // with any of the existing intervals, // print it Interval res = overlapSearch(root, appt[i]); if (res != null) Console.Write("[" + appt[i].low + "," + appt[i].high + "] Conflicts with [" + res.low + "," + res.high + "]\n"); // Insert this appointment root = insert(root, appt[i]); } } // Driver code public static void Main(String[] args) { Interval []appt = new Interval[6]; appt[0] = newNode(1, 5); appt[1] = newNode(3, 7); appt[2] = newNode(2, 6); appt[3] = newNode(10, 15); appt[4] = newNode(5, 6); appt[5] = newNode(4, 100); int n = appt.Length; Console.Write( "Following are conflicting intervals\n"); printConflicting(appt, n); } } // This code is contributed by gauravrajput1
Javascript
<script> // Javascript program to print all conflicting // appointments in a given set of appointments // Structure to represent an interval class Interval { constructor() { this.low = 0; this.high = 0; } } class ITNode { // 'i' could also be a normal variable constructor() { this.max = 0; this.left = null; this.right = null; this.i = null; } } // A utility function to create a new node function newNodeDouble(l, h) { var temp = new Interval(); temp.low = l; temp.high = h; return temp; } // A utility function to create a new node function newNodeSingle(i) { var temp = new ITNode(); temp.i = i; temp.max = i.high; temp.left = temp.right = null; return temp; } // A utility function to insert a new // Interval Search Tree Node. This is // similar to BST Insert. Here the // low value of interval is used to // maintain BST property function insert(root, i) { // Base case: Tree is empty, // new node becomes root if (root == null) return newNodeSingle(i); // Get low value of interval at root var l = root.i.low; // If root's low value is smaller, // then new interval goes to left subtree if (i.low < l) root.left = insert(root.left, i); // Else, new node goes to right subtree. else root.right = insert(root.right, i); // Update the max value of this // ancestor if needed if (root.max < i.high) root.max = i.high; return root; } // A utility function to check if given // two intervals overlap function doOVerlap(i1, i2) { if (i1.low < i2.high && i2.low < i1.high) return true; return false; } // The main function that searches a given // interval i in a given Interval Tree. function overlapSearch(root, i) { // Base Case, tree is empty if (root == null) return null; // If given interval overlaps with root if (doOVerlap(root.i, i)) return root.i; // If left child of root is present // and max of left child is greater // than or equal to given interval, // then i may overlap with an interval // is left subtree if (root.left != null && root.left.max >= i.low) return overlapSearch(root.left, i); // Else interval can only // overlap with right subtree return overlapSearch(root.right, i); } // This function prints all conflicting // appointments in a given array of appointments. function printConflicting(appt, n) { // Create an empty Interval Search // Tree, add first appointment var root = null; root = insert(root, appt[0]); // Process rest of the intervals for(var i = 1; i < n; i++) { // If current appointment conflicts // with any of the existing intervals, // print it var res = overlapSearch(root, appt[i]); if (res != null) document.write("[" + appt[i].low + "," + appt[i].high + "] Conflicts with [" + res.low + "," + res.high + "]<br>"); // Insert this appointment root = insert(root, appt[i]); } } // Driver code var appt = Array(6); appt[0] = newNodeDouble(1, 5); appt[1] = newNodeDouble(3, 7); appt[2] = newNodeDouble(2, 6); appt[3] = newNodeDouble(10, 15); appt[4] = newNodeDouble(5, 6); appt[5] = newNodeDouble(4, 100); var n = appt.length; document.write( "Following are conflicting intervals<br>"); printConflicting(appt, n); </script>
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]
Tenga en cuenta que la implementación anterior utiliza una simple operación de inserción de árbol de búsqueda binaria. Por lo tanto, la complejidad temporal de la implementación anterior es mayor que O(nLogn). Podemos usar técnicas de balanceo Red-Black Tree o AVL Tree para hacer la implementación anterior O(nLogn).
Este artículo es una contribución de Anmol . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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