Hi all! This is a problem asked on facebook interview....
There are many intervals each defined by pair containing a starting point and a ending point (si, ei). Two intervals i1 and i2 are called nested if i2 lies completely inside of i1. Example:- (2,6) and (3,4) are nested, since (3,4) is a part of (2,6). Similarly k intervals i1, i2, i3....ik are called nested if, i2 lies inside i1, i3 lies inside i2, ...and so on. Determine size of largest set of intervals from the given intervals, such that all the intervals in that set could produce a nesting.
I thought it in following way:- Let us take an e.g.- (0,7) (0,5) (1,21) (1,9) (2,8) (2,4) (3,20) (4,16) (5,15) (6,21) Sort it in the way such that a[i-1]<=a[i] && b[i-1]>=b[i] Than starting from first interval we start a linked list.. if the next interval comes inside a interval we move down the node and traverse the graph created down the node(other than main list)..we store the pointer of the maximum level node in this graph at which the new interval can fit.. and traverse further in linked list to see under whom the current interval comes.. at last we have a pointer to a node with whom we have to attach the current interval.. and compare the level of this node with the maximum level we already have..... The final value of maximum level is size of maximal nested intervals set..
complexity of above solution is likely to be:- O(n(k+l) + nlogn)
I guess it is difficult to get it this way, but I have no other option... if anyone got other algorithm.. please explain it...thanks!!
Полный текст и комментарии »