Help needed in the following problem :
There are N (1<=N<=200000) line segments (end-point coordinates are positive integers less than 1e9). The task is to merge the line segments that are overlapping and finally print the coordinates of all the merged line-segments.
Sample Test Case
N = 4
Line segments:
[(1,1) (5,1)]
[(4,1) (7,1)]
[(3,3) (9,3)]
[(5,3) (8,3)]
The answer for this test case would be :
[(1,1) (7,1)]
[(3,3) (9,3)]
My Approach : Consider each line segment as a vertex and make edges between segments U and V if U and V overlaps. Then, find the connected components. For each connected components, answer can be calculated by taking the min of left coordinates and maximum of right coordinates. But this approach is O(N^2) and will not work for N=200000.
You could group segments on the same line together (by creating a map from a slope-intercept pair to a list of segments). Then, you just have to solve the merging intervals problem on each group.
Simple and neat !!! Thanks a lot :)
I feared that we may have to use line-sweep techniques.
If your segments are all straight lines on X axis (as your example case) then i think you can group them by Y dimension and solve each separately. For solving each one you first sort them by X axis then you iterate from left to right and add +1 if you encounter an opening of a segment and -1 if you encountered a closing. When you come to 0, your interval stops (this works because every point starts on the left and ends on the right, you can think of that as having a nice form of nested parenthesis and you want to find the outer one)
No, the segments are not parallel to x-axis. They can have any slope.
oh i see, well the same idea applies here aswell. You just need to group them differently, they must have the same slope and another information (for instance from a slope you can calculate at which point it would intersect the X axis) if you find two segments with the both informations the same, they can overlap. From then on, it's really the same problem.
That is exactly what mkirsche has described in the first comment !! Simple and elegant.