Skip to main content

56. Merge Intervals

mediumAsked at Cohere

Merge all overlapping intervals in a list. Cohere asks this because interval merging directly models context-window deduplication, log event collapsing, and bounding-box merging in document-layout analysis for enterprise RAG systems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2026-Q1)— Cohere onsite candidates report Merge Intervals as a classic medium problem tested in algorithm rounds.
  • Blind (2025-11)— Mentioned in Cohere interview prep threads as a must-know interval problem.

Problem

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

Examples

Example 1

Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]

Explanation: [1,3] and [2,6] overlap so they merge to [1,6].

Example 2

Input
intervals = [[1,4],[4,5]]
Output
[[1,5]]

Explanation: Touching intervals ([1,4] and [4,5]) are considered overlapping.

Approaches

1. Sort by start + greedy merge

Sort intervals by start time. Walk through them: if the current interval overlaps with the last merged interval (current.start <= last.end), extend the last interval's end. Otherwise push the current interval as a new segment.

Time
O(n log n)
Space
O(n)
function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    const curr = intervals[i];
    if (curr[0] <= last[1]) {
      last[1] = Math.max(last[1], curr[1]); // extend
    } else {
      result.push(curr);
    }
  }
  return result;
}

Tradeoff: O(n log n) dominated by sorting. The merge pass itself is O(n). This is optimal for comparison-based algorithms.

Cohere-specific tips

Cohere may extend this to Insert Interval (LC 57) — insert a new interval into an already-merged list without re-sorting. Practise that variant since it tests binary search and selective merging. Also, mention the context-window application: 'In document chunking for retrieval, overlapping text spans from multiple extractors must be merged so we don't feed duplicate context to the model — same algorithm.'

Common mistakes

  • Not sorting first — without sorting, non-adjacent intervals in the input may be missed.
  • Using curr[1] instead of Math.max(last[1], curr[1]) — a fully-contained interval would shrink the last interval incorrectly.
  • Modifying intervals in-place and corrupting subsequent iteration — either sort a copy or work carefully.
  • Off-by-one in overlap check — curr[0] <= last[1] (not <) because touching intervals merge.

Follow-up questions

An interviewer at Cohere may pivot to one of these next:

  • Insert Interval (LC 57) — insert a new interval into a sorted, merged list.
  • Non-overlapping Intervals (LC 435) — minimum removals to make intervals non-overlapping.
  • How would you merge intervals in a streaming setting where new intervals arrive continuously?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why sort by start rather than end?

Sorting by start ensures that when we process an interval, all potentially overlapping intervals have already been encountered (since they must start at or before the current interval).

Does this handle touching intervals (end == start of next)?

Yes — the condition curr[0] <= last[1] treats touching intervals as overlapping and merges them.

What if intervals is already sorted?

Skip the sort and run in O(n). Mention this optimisation when the interviewer confirms sorted input.

Practice these live with InterviewChamp.AI

Drill Merge Intervals and other Cohere interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →