Interval problems usually ask you to combine overlapping ranges or process events happening over time.

The core merge sweep with the max() trick that everyone gets wrong:

Merge Intervals

Merge overlapping intervals into disjoint blocks in one sweep.

Sort by start, keep a current block, and extend its end with max(cur.end, e) whenever the next starts inside it. Using max (not the raw end) is the key detail — a nested interval can end earlier without shrinking the merged block. O(n log n).

ARRAY VISUALIZER

Steps –

1-4

2-5

3-6

7-9

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        sort intervals by start
                      
                        2
                        cur = first interval
                      
                        3
                        for each next (s, e):
                      
                        4
                          if s <= cur.end: cur.end = max(cur.end, e)
                      
                        5
                          else: output cur; cur = this interval

The main idea is:

Sort intervals first, then process them from left to right.

Focus on recognizing:

“Overlapping intervals” + “Merge” = Sort + Merge

“Buildings” + “Height changes” = Sweep Line + Heap

Pattern Table

Pattern	Typical Questions	Trigger
Merge Intervals	Merge overlapping	Sort by start + extend end
Insert Interval	Insert and merge	Compare with current interval
Skyline	Building silhouette	Sweep line + height events

Mental Trigger

Sort → Process from left to right → Merge or handle events.

1. Generic Interval Merge Template (Base)

This is the main interval merging template.

public int[][] merge(int[][] intervals) {

    Arrays.sort(intervals, (a, b) ->
        Integer.compare(a[0], b[0])
    );

    List<int[]> merged = new ArrayList<>();

    for (int[] interval : intervals) {

        // No overlap
        if (merged.isEmpty() ||
            merged.get(merged.size() - 1)[1] < interval[0]) {

            merged.add(interval);

        } else {

            // Overlap
            int lastEnd =
                merged.get(merged.size() - 1)[1];

            merged.get(merged.size() - 1)[1] =
                Math.max(lastEnd, interval[1]);
        }
    }

    return merged.toArray(new int[merged.size()][]);
}

def merge(intervals):
    intervals.sort(key=lambda x: x[0])

    merged = []

    for interval in intervals:
        # No overlap
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # Overlap
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[0] < b[0];
         });

    vector<vector<int>> merged;

    for (vector<int>& interval : intervals) {
        // No overlap
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            // Overlap
            merged.back()[1] = max(merged.back()[1], interval[1]);
        }
    }

    return merged;
}

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [];

  for (const interval of intervals) {
    // No overlap
    if (merged.length === 0 ||
        merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      // Overlap
      const last = merged[merged.length - 1];

      last[1] = Math.max(last[1], interval[1]);
    }
  }

  return merged;
}

How the Base Template Works

Suppose:

[1,3]
[2,6]
[8,10]

First:

[1,3]

Next interval starts at 2.

2 <= 3

So they overlap.

Merge:

[1,6]

8 > 6

No overlap.

Add:

[8,10]

Final:

[1,6]
[8,10]

Merge Intervals = Sort by start + Check overlap + Extend end.

Pattern 1: Merge Overlapping Intervals

Detection Cues

Look for:

Merge overlapping ranges
Combine intervals
Remove redundant overlapping intervals
Return non-overlapping intervals

Java Code

public int[][] merge(int[][] intervals) {

    Arrays.sort(intervals, (a, b) ->
        Integer.compare(a[0], b[0])
    );

    List<int[]> result = new ArrayList<>();

    for (int[] interval : intervals) {

        if (result.isEmpty() ||
            result.get(result.size() - 1)[1] < interval[0]) {

            result.add(interval);

        } else {

            result.get(result.size() - 1)[1] =
                Math.max(
                    result.get(result.size() - 1)[1],
                    interval[1]
                );
        }
    }

    return result.toArray(new int[result.size()][]);
}

def merge(intervals):
    intervals.sort(key=lambda x: x[0])

    result = []

    for interval in intervals:
        if not result or result[-1][1] < interval[0]:
            result.append(interval)
        else:
            result[-1][1] = max(result[-1][1], interval[1])

    return result

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[0] < b[0];
         });

    vector<vector<int>> result;

    for (vector<int>& interval : intervals) {
        if (result.empty() || result.back()[1] < interval[0]) {
            result.push_back(interval);
        } else {
            result.back()[1] = max(result.back()[1], interval[1]);
        }
    }

    return result;
}

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  const result = [];

  for (const interval of intervals) {
    if (result.length === 0 ||
        result[result.length - 1][1] < interval[0]) {
      result.push(interval);
    } else {
      const last = result[result.length - 1];

      last[1] = Math.max(last[1], interval[1]);
    }
  }

  return result;
}

What Changed from the Base?

Nothing.

This is the base pattern.

The important decision is:

lastEnd < currentStart

If true:

No overlap → Add interval

Otherwise:

Overlap → Extend end

No overlap → Add. Overlap → Extend.

Pattern 2: Insert an Interval

Detection Cues

Add a new interval
Merge it with existing intervals
Existing intervals are already sorted

Java Code

public int[][] insert(int[][] intervals, int[] newInterval) {

    List<int[]> result = new ArrayList<>();

    int i = 0;

    // Intervals completely before newInterval
    while (i < intervals.length &&
           intervals[i][1] < newInterval[0]) {

        result.add(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < intervals.length &&
           intervals[i][0] <= newInterval[1]) {

        newInterval[0] =
            Math.min(newInterval[0], intervals[i][0]);

        newInterval[1] =
            Math.max(newInterval[1], intervals[i][1]);

        i++;
    }

    // Add merged interval
    result.add(newInterval);

    // Remaining intervals
    while (i < intervals.length) {
        result.add(intervals[i]);
        i++;
    }

    return result.toArray(new int[result.size()][]);
}

def insert(intervals, new_interval):
    result = []

    i = 0

    # Intervals completely before newInterval
    while i < len(intervals) and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1

    # Add merged interval
    result.append(new_interval)

    # Remaining intervals
    while i < len(intervals):
        result.append(intervals[i])
        i += 1

    return result

vector<vector<int>> insert(vector<vector<int>>& intervals,
                           vector<int>& newInterval) {
    vector<vector<int>> result;

    int i = 0;

    // Intervals completely before newInterval
    while (i < (int)intervals.size() &&
           intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < (int)intervals.size() &&
           intervals[i][0] <= newInterval[1]) {
        newInterval[0] =
            min(newInterval[0], intervals[i][0]);

        newInterval[1] =
            max(newInterval[1], intervals[i][1]);

        i++;
    }

    // Add merged interval
    result.push_back(newInterval);

    // Remaining intervals
    while (i < (int)intervals.size()) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

function insert(intervals, newInterval) {
  const result = [];

  let i = 0;

  // Intervals completely before newInterval
  while (i < intervals.length &&
         intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Merge overlapping intervals
  while (i < intervals.length &&
         intervals[i][0] <= newInterval[1]) {
    newInterval[0] =
      Math.min(newInterval[0], intervals[i][0]);

    newInterval[1] =
      Math.max(newInterval[1], intervals[i][1]);

    i++;
  }

  // Add merged interval
  result.push(newInterval);

  // Remaining intervals
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

What Changed from the Base?

1. Added a new interval

Base:

for (int[] interval : intervals)

Changed to:

int[] newInterval

because we have one interval that needs to be inserted.

2. Separate intervals into three groups

Before new interval
        ↓
Overlapping intervals
        ↓
After new interval

3. Merge into `newInterval`

Added:

newInterval[0] =
    Math.min(newInterval[0], intervals[i][0]);

newInterval[1] =
    Math.max(newInterval[1], intervals[i][1]);

Insert Interval = Find position → Merge overlaps → Add remaining intervals.

Pattern 3: Skyline Problem

The skyline problem is different from normal interval merging.

Instead of asking:

“Do these intervals overlap?”

we ask:

“What is the maximum height at this x-coordinate?”

So we use a sweep line.

Java Code

public List<List<Integer>> getSkyline(int[][] buildings) {

    List<int[]> events = new ArrayList<>();

    // Create start and end events
    for (int[] building : buildings) {

        int start = building[0];
        int end = building[1];
        int height = building[2];

        events.add(new int[]{start, -height});
        events.add(new int[]{end, height});
    }

    // Sort by x-coordinate
    // At the same x:
    // starts (-height) come before ends
    events.sort((a, b) -> {

        if (a[0] != b[0]) {
            return Integer.compare(a[0], b[0]);
        }

        return Integer.compare(a[1], b[1]);
    });

    List<List<Integer>> result = new ArrayList<>();

    // Max-heap for active building heights
    PriorityQueue<Integer> pq =
        new PriorityQueue<>(Collections.reverseOrder());

    pq.offer(0);

    int previousHeight = 0;

    for (int[] event : events) {

        int x = event[0];
        int height = event[1];

        // Start event
        if (height < 0) {
            pq.offer(-height);
        }

        // End event
        else {
            pq.remove(height);
        }

        int currentHeight = pq.peek();

        // Height changed
        if (currentHeight != previousHeight) {

            result.add(
                Arrays.asList(x, currentHeight)
            );

            previousHeight = currentHeight;
        }
    }

    return result;
}

import heapq

def get_skyline(buildings):
    events = []

    # Create start and end events
    for start, end, height in buildings:
        events.append((start, -height))
        events.append((end, height))

    # Sort by x-coordinate
    # At the same x:
    # starts (-height) come before ends
    events.sort()

    result = []

    # Max-heap for active building heights (negated)
    live = [0]

    previous_height = 0

    for x, height in events:
        # Start event
        if height < 0:
            heapq.heappush(live, -height)
        # End event
        else:
            live.remove(-height)

        current_height = -live[0]

        # Height changed
        if current_height != previous_height:
            result.append([x, current_height])
            previous_height = current_height

    return result

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<pair<int, int>> events;

    // Create start and end events
    for (auto& building : buildings) {
        events.push_back({building[0], -building[2]});
        events.push_back({building[1], building[2]});
    }

    // Sort by x-coordinate
    // At the same x:
    // starts (-height) come before ends
    sort(events.begin(), events.end());

    vector<vector<int>> result;

    // Max-heap for active building heights (multiset bag)
    multiset<int> live;
    live.insert(0);

    int previousHeight = 0;

    for (auto& [x, h] : events) {
        // Start event
        if (h < 0) {
            live.insert(-h);
        }
        // End event
        else {
            live.erase(live.find(h));
        }

        int currentHeight = *live.rbegin();

        // Height changed
        if (currentHeight != previousHeight) {
            result.push_back({x, currentHeight});
            previousHeight = currentHeight;
        }
    }

    return result;
}

// ponytail: array stands in for the max-heap; Math.max per event is O(n²), fine for lesson sizes
function getSkyline(buildings) {
  const events = [];

  // Create start and end events
  for (const [start, end, height] of buildings) {
    events.push([start, -height]);
    events.push([end, height]);
  }

  // Sort by x-coordinate
  // At the same x:
  // starts (-height) come before ends
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

  const result = [];

  const live = [0];

  let previousHeight = 0;

  for (const [x, height] of events) {
    // Start event
    if (height < 0) {
      live.push(-height);
    }
    // End event
    else {
      live.splice(live.indexOf(height), 1);
    }

    const currentHeight = Math.max(...live);

    // Height changed
    if (currentHeight !== previousHeight) {
      result.push([x, currentHeight]);

      previousHeight = currentHeight;
    }
  }

  return result;
}

What Changed from the Base?

1. Intervals became events

Base:

int[] interval

Changed:

int[] event

Each building creates two events:

events.add(new int[]{start, -height});
events.add(new int[]{end, height});

Meaning:

-negative height → building starts
positive height  → building ends

2. Added a max-heap

Base:

List<int[]> merged

Changed:

PriorityQueue<Integer> pq

because we need to know:

What is the tallest building currently active?

The heap always gives us:

pq.peek()

= current maximum height.

3. Sweep from left to right

Base:

// Merge intervals

Changed:

for (int[] event : events)

because skyline is about height changes at specific x-coordinates.

4. Add a point only when height changes

Added:

if (currentHeight != previousHeight)

because we only want important skyline points.

Skyline = Convert buildings to events + Sweep left to right + Max-heap for current height.

Why Negative Height for Start Events?

We use:

start → -height
end   → height

Example:

Building:
[2, 9, 10]

becomes:

(2, -10)   start
(9, 10)    end

Negative values make start events easy to identify:

if (height < 0)

They also help sorting when multiple events happen at the same x-coordinate.

Interval Pattern Evolution

Base: Merge Intervals
        ↓
Sort by start
        ↓
Check overlap
        ↓
Extend end
        ↓
Insert Interval
(+ new interval + merge around it)
        ↓
Skyline
(+ events + sweep line + max-heap)

Common Mistakes

1. Forgetting to sort

Wrong:

for (int[] interval : intervals)

without sorting.

Correct:

Arrays.sort(intervals,
    (a, b) -> Integer.compare(a[0], b[0]));

2. Using the current end instead of `max`

Wrong:

lastEnd = interval[1];

Correct:

lastEnd = Math.max(lastEnd, interval[1]);

Example:

[1,10]
[2,5]

The merged interval must remain:

[1,10]

not:

[1,5]

3. Wrong overlap condition

For intervals:

[1,3]
[3,5]

If touching intervals can be merged:

currentStart <= lastEnd

If touching intervals are considered separate:

currentStart > lastEnd

Use the condition required by the problem.

4. Using a normal queue for Skyline

Wrong:

Queue<Integer>

We need the maximum active height.

Use:

PriorityQueue<Integer> pq =
    new PriorityQueue<>(Collections.reverseOrder());

5. Adding every skyline event

Don’t add a point every time an event occurs.

Only add when:

currentHeight != previousHeight

Recognition Cheat Sheet

If you see…	Think…
Merge overlapping intervals	Sort + Merge
Combine ranges	Sort + Merge
Insert and merge interval	Two pointers + Merge
Meeting conflicts	Interval processing
Building silhouette	Skyline
Height changes over x	Sweep Line
Maximum active height	Max-Heap
Events at positions	Sweep Line

Simple Mental Model

Merge Intervals

Sort → Check overlap → Extend end → Continue

Insert Interval

Before → Merge overlaps → After

Skyline

Create events → Sort → Sweep → Track maximum height

Earn Premium with Referrals

Merge Intervals

Pattern Table

Mental Trigger

1. Generic Interval Merge Template (Base)

How the Base Template Works

Pattern 1: Merge Overlapping Intervals

Detection Cues

Java Code

What Changed from the Base?

Pattern 2: Insert an Interval

Detection Cues

Java Code

What Changed from the Base?

1. Added a new interval

2. Separate intervals into three groups

3. Merge into newInterval

Pattern 3: Skyline Problem

Java Code

What Changed from the Base?

1. Intervals became events

2. Added a max-heap

3. Sweep from left to right

4. Add a point only when height changes

Why Negative Height for Start Events?

Interval Pattern Evolution

Common Mistakes

1. Forgetting to sort

2. Using the current end instead of max

3. Wrong overlap condition

4. Using a normal queue for Skyline

5. Adding every skyline event

Recognition Cheat Sheet

Simple Mental Model

Merge Intervals

Insert Interval

Skyline

Premium Content

My Private Notes

3. Merge into `newInterval`

2. Using the current end instead of `max`