Блог пользователя ddt

Автор ddt, 10 лет назад, По-английски

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
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Simple and neat !!! Thanks a lot :)
    I feared that we may have to use line-sweep techniques.

»
10 лет назад, # |
  Проголосовать: нравится 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)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No, the segments are not parallel to x-axis. They can have any slope.

    • »
      »
      »
      10 лет назад, # ^ |
      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.