### ddt's blog

By ddt, 5 years ago, ,

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.

• +3

 » 5 years ago, # |   +6 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.
•  » » 5 years ago, # ^ |   +1 Simple and neat !!! Thanks a lot :) I feared that we may have to use line-sweep techniques.
 » 5 years ago, # |   0 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)
•  » » 5 years ago, # ^ |   0 No, the segments are not parallel to x-axis. They can have any slope.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 years ago, # ^ |   0 That is exactly what mkirsche has described in the first comment !! Simple and elegant.