InternDoor

Join the overlapping stretches

Mediumarrays · sorting · intervals

Reported in interviews at (where)

Each intervals[i] = [start, end] is a stretch of the number line, with start <= end. Two stretches that overlap, or touch at an end point, belong together.

Join every group of stretches that belong together into one stretch, and return the result sorted by start.

Example 1
Input
intervals = [[8,9],[1,4],[3,5],[9,12]]
Output
[[1,5],[8,12]]

[1, 4] and [3, 5] overlap; [8, 9] and [9, 12] touch at 9.

Example 2
Input
intervals = [[5,5],[1,2]]
Output
[[1,2],[5,5]]

Nothing overlaps, so the two stretches only need sorting. A stretch may be a single point.

Limits

  • 1 <= intervals.length <= 100000
  • 0 <= start <= end <= 1000000000

Hints

Hint 1

Sort the stretches by start. Then any stretch that belongs with an earlier one belongs with the last one you kept.

Hint 2

Keep a list of joined stretches. A new stretch whose start is at most the last end extends it; otherwise it starts a new one.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.