Problem Link - Moving Segments
Problem Statement -
N line segments (numbered 1 through N) are placed on the x-axis. For each valid i, the i-th segment starts at x = L_i and ends at x = R_i.
At the time t = 0, all segments start moving; for each valid i, the i-th segment starts moving with speed V_i. You need to assign a direction - left or right - to the movement of each segment, i.e. choose a sign for each V_i (not necessarily the same for all segments). The resulting movement must satisfy the following condition: at the time t = 10^{10000}, there are no two segments that touch or intersect.
Decide if it is possible to assign directions to the segments in such a way that the above condition is satisfied.
Approach -
To check if segments can move without intersecting, we use a sweeping line approach to detect overlaps. Each segment has a start and end point on the x-axis, moving at a specified speed. We group segments by speed to handle those with identical speeds together. Sorting segments by speed, we then track overlaps using a frequency map, which increments at each segment’s start and decrements after its end. By calculating a running total with this map, we detect areas where three or more segments overlap, indicating inevitable collisions. If this count never reaches three, a collision-free arrangement is possible.
Time Complexity -
O(NlogN), due to sorting and the frequency map operations.
Space Complexity -
O(N), for storing segment intervals and frequency maps.