Interview Question


giving lots of intervals [ai, bi], find a point intersect

  with the most number of intervals.

Interview Answer

5 Answers


only come up with n^2 method in the interview process. interval tree crossed my mind, but too complex to implement in a short time. They are looking for nlgn solution, which I came up after interview. wtf. intervals = [[a1, b1], [a2, b2], ..., [an, bn]] sort(intervals); priority_queue q; int res = 0, point = -1; for (int i = 0; i < n; i++) { q.enqueue(b[i]); if (q.size() > res) { res = q.size(); point = q.front(); } if (a[i] > q.front()) while (a[i] > q.front()) q.dequeue(); } // res is the numbers of intersections, point is the number.

Interview Candidate on Mar 1, 2012

How do you sort the intervals?

Interested on Mar 8, 2012

First solution is correct. The assumption is, the point is definitely one of ai. Then quicksort intervals by ai for each intervals, queue.insert (bi) while( queue_head < ai) queue.pop() updatemax(ai, queue.size)

buptrain on Mar 20, 2012

Jeez, how many times have they asked this same question?

Anonymous on Apr 9, 2012

I suspect the answer given by both the candidate and buptrain. If you look at this sorted interval group: (1,10), (2,5), (7,9). The algorithm returns 3 as # of intersections and return 10 as the point, which is obviously wrong. (1): ********** (2): **** (3): *** The key problem here (or some additional assumption not specified by candidate) is the length of each interval varies, thus the next interval may have a shorter end value than the previous one even the start value is larger.

Anonymous on Apr 12, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.