Given n appointments, find all conflicting appointments - GeeksforGeeks
http://flexaired.blogspot.com/2013/04/conflicting-appointments-from-given.html
https://techinterviewnow.wordpress.com/2011/07/29/conflicting-appoinments/
https://www.glassdoor.com/Interview/If-you-had-a-list-of-appointments-each-appointment-has-a-begin-time-an-end-time-and-a-boolean-hasConflict-how-would-yo-QTN_120704.htm
Read full article from Given n appointments, find all conflicting appointments - GeeksforGeeks
Given n appointments, find all conflicting appointments
Given n appointments, find all conflicting appointments.
Examples:
Examples:
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]An appointment is conflicting, if it conflicts with any of the previous appointments in array.A Simple Solution is to one by one process all appointments from second appointment to last. For every appointment i, check if it conflicts with i-1, i-2, … 0. The time complexity of this method is O(n2).
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.
O(NLogN)
struct Interval{ int low, high;};// Structure to represent a node in Interval Search Treestruct ITNode{ Interval *i; // 'i' could also be a normal variable int max; ITNode *left, *right;};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;}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);}oid 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]); }}http://flexaired.blogspot.com/2013/04/conflicting-appointments-from-given.html
public static void findConflictingEvents() { |
Arrays.sort(events, new startEventComparator()); |
printEvents(); |
int len = events.length; |
for (int i = 0; i < len; i++) { |
int low = i + 1; |
int high = len - 1; |
int key = events[i].end; |
int keyId = events[i].id; |
int index = 0; |
while (low <= high) { |
int mid = (int) Math.floor((low + high) / 2); |
if (key >= events[mid].start |
&& ((mid + 1 < len) && (key <= events[mid + 1].start))) { |
low = mid; |
index = mid; |
break; |
} else if (key >= events[mid].start) { |
low = mid + 1; |
} else { |
high = mid - 1; |
} |
} |
ArrayList<Integer> evtList = eventConflicts.get(keyId); |
low = low > high ? high : low; |
for (int k = i + 1; k <= low && k < len; k++) { |
if (k == i) { |
continue; |
} |
evtList.add(events[k].id); |
ArrayList<Integer> invList = eventConflicts.get(events[k].id); |
invList.add(keyId); |
eventConflicts.put(events[k].id, invList); |
} |
eventConflicts.put(keyId, evtList); |
} |
System.out.println("Conflicts are: "); |
Iterator iterMap = eventConflicts.entrySet().iterator(); |
while (iterMap.hasNext()) { |
Map.Entry<Integer, ArrayList> pair = (Map.Entry) iterMap.next(); |
System.out.print(pair.getKey() + " <> "); |
Iterator iter = pair.getValue().iterator(); |
while (iter.hasNext()) { |
System.out.print(iter.next() + " "); |
} |
System.out.println(); |
} |
} |
An optimal solution is to first sort the appointments by their start time. Quicksort will give us a running time of O(n log n). Once the appointments are sorted we just need to make sure that for each appointment, it doesn’t start before whatever the latest appointment was so far. So we just iterate through each appointment keeping track of the appointment with the latest end time. For each appointment we check to see if the meeting starts before that latest meeting ends.
public void findConflicts(List<Appointment> appts) {
Appointment latest = null;
Iterator<Appointment> iter = appts.iterator();
while(iter.hasNext()) {
Appointment next = iter.next();
if(latest != null && next.start < latest.end) {
next.hasConflict = true;
latest.hasConflict = true;
}
if(latest == null || next.end > latest.end) {
latest = next;
}
}
}
http://karmaandcoding.blogspot.com/2012/01/find-all-conflicting-appointments-from.html
If you had a list of appointments (each appointment has a
begin time, an end time, and a boolean hasConflict), how would you efficiently go through them and set the hasConflict boolean for each. You cannot assume they are sorted in any way. Keep in mind that one appointment may be very long, etc.
Read full article from Given n appointments, find all conflicting appointments - GeeksforGeeks
