Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

FInd overlapping appointments in O(n) time?

Tags:

I was recently asked this question in an interview. Even though I was able to come up the O(n²) solution, the interviewer was obsessed with an O(n) solution. I also checked few other solutions of O(n logn) which I understood, but O(n) solution is still not my cup of tea which assumes appointments sorted by start-time.

Can anyone explain this?

Problem Statement: You are given n appointments. Each appointment contains a start time and an end time. You have to retun all conflicting appointments efficiently.

Person: 1,2, 3, 4, 5
App Start: 2, 4, 29, 10, 22
App End: 5, 7, 34, 11, 36

Answer: 2x1 5x3

O(n logn) algorithm: separate start and end point like this:

2s, 4s, 29s, 10s, 22s, 5e, 7e, 34e, 11e, 36e

then sort all of this points (for simplicity let's assume each point is unique):

2s, 4s, 5e, 7e, 10s, 11e, 22s, 29s, 34e, 36e

if we have consecutive starts without ends then it is overlapping: 2s, 4s are adjacent so overlapping is there

We will keep a count of "s" and each time we encounter it will +1, and when e is encountered we decrease count by 1.

like image 925
Dude Avatar asked Sep 05 '12 14:09

Dude


People also ask

How do you find overlapping?

1) Sort all intervals in increasing order of start time. This step takes O(nLogn) time. 2) In the sorted array, if start time of an interval is less than end of previous interval, then there is an overlap.

How can we prevent overlapping appointments?

Answer: We can avoid the overlapped appointments by using IsSlotAvailable public method which helps to check whether the given time slots already exist in events. So, based on the Boolean value we can prevent the event using Cancel argument of OnActionBegin event. args.

What is conflicting appointment?

An appointment is conflicting if it conflicts with any of the previous appointments in the array. We strongly recommend to minimize the browser and try this yourself first. A Simple Solution is to one by one process all appointments from the second appointment to last.


1 Answers

The general solution to this problem is not possible in O(n).

At a minimum you need to sort by appointment start time, which requires O(n log n).

There is an O(n) solution if the list is already sorted. The algorithm basically involves checking whether the next appointment is overlapped by any previous ones. There is a bit of subtlety to this one as you actually need two pointers into the list as you run through it:

  • The current appointment being checked
  • The appointment with the latest end time encountered so far (which might not be the previous appointment)

O(n) solutions for the unsorted case could only exist if you have other constraints, e.g. a fixed number of appointment timeslots. If this was the case, then you can use HashSets to determine which appointment(s) cover each timeslot, algorithm roughly as follows:

  • Create a HashSet for each timeslot - O(1) since timeslot number is a fixed constant
  • For each appointment, store its ID number in HashSets of slot(s) that it covers - O(n) since updating a constant number of timeslots is O(1) for each appointment
  • Run through the slots, checking for overlaps - O(1) (or O(n) if you want to iterate over the overlapping appointments to return them as results)
like image 110
mikera Avatar answered Sep 22 '22 04:09

mikera