How should I practice Merge Collinear Point Segments?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Applied Intuition phone screen problems in FastPrep.

Is Merge Collinear Point Segments associated with Applied Intuition?

FastPrep tags this as a Applied Intuition phone screen coding practice problem when the problem catalog has that company and stage context.

Merge Collinear Point Segments

Applied Intuition● HardFULLTIMEPHONE SCREEN

Learn

Problem statement

Each input segment is a list of at least two distinct integer points lying on one straight line. Treat its closed geometric span as the interval between its extreme points.

Merge segments that lie on the same infinite line and whose closed spans overlap or touch. A merged result contains the distinct listed points from its component, ordered along a canonical direction. Lines are returned in the order they first appear in the input; disjoint components on one line are returned by increasing position along that line.

The rule applies to every slope, including horizontal and vertical lines.

Function

mergeCollinearSegments(segments: int[][][]) → int[][][]

Examples

Example 1

segments = [[[1,1],[2,2],[4,4]],[[2,1],[4,2]],[[3,3],[6,6]],[[7,7],[8,8]]]return = [[[1,1],[2,2],[3,3],[4,4],[6,6]],[[7,7],[8,8]],[[2,1],[4,2]]]

The first and third segments overlap on y=x. The later y=x component is disjoint, and the slope-one-half line remains separate.

Example 2

segments = [[[-2,3],[0,3],[2,3]],[[2,3],[5,3]],[[1,-1],[1,2]]]return = [[[-2,3],[0,3],[2,3],[5,3]],[[1,-1],[1,2]]]

Horizontal segments merge at their touching endpoint, while the vertical segment belongs to another line.

Constraints

1 <= segments.length <= 5000.
Each segment contains at least two distinct points and all of its points are collinear.
The total number of listed points is at most 20000.
Coordinates are integers in [-10^6,10^6].