algorithm - FInd overlapping appointments in O(n) time?

Question

I was recently asked this question in an interview. Even though I was able to come up the O(n2) 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.

Answer 1

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)