Internet Question Interview Question
Site Reliability EngineersTeam: N/A
Country: United States
1)if it is to be done in O(N) time , that means the list of people with starting and ending time could be traversed at most once. Now this can only lead to us towards a solution , if the list of people was already sorted according to the starting time . Then we can just check the consecutive element's starting time & ending time and decide whether they overlap or not .
2) Other wise we can sort the list of people according to the start time , which will anyway require a pre processing time of O(NlogN) & then a O(N) search as stated in 1 . So eventually it is O(N) .
3) last which I can think of is to overcome the sorting effort , that can be done by keeping the state of the previous persons start and end time . We can do so by some kind of hash table , where we hash according to the start time . when ever any persons start time falls in a bucket , we search in that bucket with all other persons to figure out the overlap . But this is also not O(N) theoretically , as small buckets can be of size N at the worst case , hence leading to O(N) .
Very neat solution. I worked out an O(nlog(n)) solution using binary tree, but yours is clearly better. For O(n) I worked out a similar solution (that space complexity depends on range of time) but you reminded me that we could make a hash function and divide (min,max) time range into n buckets, so "on average" this should be roughly O(n) and certainly better than O(nlog(n))
i think instead of checking consecutive elements starting and ending point, keep track of maxima of ending point and check whether current one's ending point is less than that or not. This will cover all cases
An idea - quantize / discretize the intervals as coarsely as practical, and have an array of quanta covering the range of all the intervals. For each person's interval, fill in all the covered quanta. If the quantum is already filled, they've collided with someone. You have to do this twice, because the first person eg won't know whether he's collided with anyone otherwise. It's all still O(n). If you don't need infinite, split-second precision.
1. Iterate through all the elements (0..N-1) in a loop.
2. if ((f[i+1] > f[i]) && s[i+1]>f[i])) AND ((f[i] > f[i-1]) && (s[i]>f[i-1)) THEN
mark the ith person overlap-free.
Here, one needs to take care about the value of 'i' not falling of the edges of the range i.e (0..N-1).
Also, f[i] = finish time of ith person
s[i] = start time of ith person.
ASSUMPTION: Persons are already sorted on their finish times.
isn't a greedy problem??
- Hector January 30, 2012