algorithm - Grouping intervals in a few passes -
i have lots of intervals (x,y) , group them together. rule set of intervals in same group if nested in 1 member of group except 1 largest interval nested in. example, (1,7), (2,4),(2,9), (8,9) can split 2 groups (1,7),(2,4) , (2,9),(8,9). of course not unique minimal in sense can't have fewer groups.
to make more complicated can't afford read in data @ once large.
i can sort data offline first element in each pair, example.
what algorithm problem?
sort intervals nondecreasing x, breaking ties nonincreasing y. scan intervals in order. while there exist more intervals, make first 1 remaining enclosing interval of new group and, while possible, add each successive interval group.
suppose there exist 2 intervals [x, y] , [x', y'] such x <= x' <= y' <= y. can show [x', y'] not enclosing interval of group, , hence grouping minimal. if [x, y] = [x', y'], clear [x, y] , [x', y'] assigned same group. otherwise, interval [x, y] sorts before [x', y'], since either x < x', or x = x' , y' < y. enclosing interval [x'', y''] active when [x', y'] scanned satisfies x'' <= x' (by sort order) , y' <= y <= y'' (since y coordinate of active enclosing interval nondecreasing on time). hence, [x', y'] not start group.
Comments
Post a Comment