56. Merge Intervals
mediumAsked at AtlassianMerge Intervals is an Atlassian-favorite scheduling problem. Given an array of intervals [start, end], merge all overlapping ones and return the result. It maps directly to calendar coalescing in Atlassian's Confluence calendars and Jira time-tracking UIs.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Atlassian loops.
- Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports cite Merge Intervals as a recurring scheduling/calendar problem.
- Blind (2025-10)— Atlassian Senior-engineer threads mention Merge Intervals as the warm-up before Meeting Rooms II.
Problem
Given an array of intervals where intervals[i] = [start_i, end_i], 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^4intervals[i].length == 20 <= start_i <= end_i <= 10^4
Examples
Example 1
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]Explanation: [1,3] and [2,6] overlap so they merge into [1,6].
Example 2
intervals = [[1,4],[4,5]][[1,5]]Explanation: Touching intervals are considered overlapping.
Approaches
1. Brute O(n^2) pairwise merge
Repeatedly scan all pairs; merge any overlapping pair into one; restart until no more merges happen.
- Time
- O(n^2)
- Space
- O(n)
function mergeBrute(intervals) {
let result = intervals.slice();
let changed = true;
while (changed) {
changed = false;
outer: for (let i = 0; i < result.length; i++) {
for (let j = i + 1; j < result.length; j++) {
const [a, b] = result[i];
const [c, d] = result[j];
if (a <= d && c <= b) {
result[i] = [Math.min(a, c), Math.max(b, d)];
result.splice(j, 1);
changed = true;
continue outer;
}
}
}
}
return result;
}Tradeoff: Easy to explain in 30 seconds but obviously slow. Useful only to motivate the sort-first insight. Mention it, then immediately move to the sorted version.
2. Sort by start, single-pass merge (optimal)
Sort by start. Walk left-to-right; if the current interval's start <= the previous interval's end, extend the previous end; otherwise push the current interval as a new group.
- Time
- O(n log n)
- Space
- O(n) for the output
function merge(intervals) {
if (intervals.length === 0) return [];
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0].slice()];
for (let i = 1; i < intervals.length; i++) {
const last = result[result.length - 1];
const [start, end] = intervals[i];
if (start <= last[1]) {
last[1] = Math.max(last[1], end);
} else {
result.push([start, end]);
}
}
return result;
}Tradeoff: n log n from the sort dominates the linear scan. Mutates the result's last entry in place for clarity; you could push immutable copies but it costs an extra allocation per merge. Atlassian's preferred shape.
Atlassian-specific tips
Atlassian interviewers consistently ask 'what's the convention if two intervals touch at a point — say [1,4] and [4,5]?'. LeetCode treats them as overlapping. State the convention out loud before coding; failing to confirm this is the #1 lost-point on Atlassian's interview rubric for this question. After you finish, expect the follow-up 'now insert a new interval into an already-merged set' (LeetCode 57).
Common mistakes
- Sorting by end instead of start — silently breaks merging on inputs like [[1,5],[2,3],[4,6]].
- Mutating the input intervals[i] in place when copying into the result — the next test case sees corrupted state if the judge runs them in sequence.
- Off-by-one on the touching-endpoint test — using < instead of <= drops [[1,4],[4,5]] into two intervals instead of [[1,5]].
Follow-up questions
An interviewer at Atlassian may pivot to one of these next:
- Insert Interval (LeetCode 57) — given an already-sorted, already-merged list, insert a new interval in O(n).
- Meeting Rooms II (LeetCode 253) — how many rooms (concurrent overlaps) do you need? Heap of end-times, or sweep-line.
- Interval Intersection (LeetCode 986) — given two sorted lists, return their intersection.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Do I need to sort or can I use a different structure?
You need sorted order. You could use a self-balancing BST keyed on start for O(log n) inserts if the input were streaming, but for the static problem nothing beats sort + single-pass.
Why does Atlassian like this problem?
Because it's the same algorithm as 'collapse overlapping calendar events into a single block' which is what Confluence calendars and Jira time-logging UIs do internally. Interviewers will explicitly probe whether you see the connection.
Free learning resources
Curated free links for this problem.