Mastering Interval Problems: A Pattern-Based Guide

Introduction

Interval problems involve tasks defined by a start and end (e.g. time spans, index ranges). They are ubiquitous in coding interviews and competitive programming, covering scenarios from scheduling meetings to merging date ranges. Mastering these problems is easier by recognizing common patterns. This guide progresses from beginner-friendly patterns to advanced techniques, illustrating how to identify each pattern and apply it step-by-step. We will focus on patterns such as Merge Intervals, Insert Interval, Two-Interval Intersections, Interval Scheduling (selection), Meeting Rooms (partitioning), and the Sweep Line algorithm. For each pattern, we explain the approach in detail, discuss typical use-cases, outline decision-making logic, offer tips and tricks, and provide a visual or analogy where helpful. Each pattern section also includes a well-commented JavaScript example and a set of 10 practice problems (easy, medium, and hard) popular in interviews, to reinforce your understanding.

Merge Intervals Pattern

The Merge Intervals pattern is about consolidating overlapping intervals into combined ranges. The core idea is to sort intervals by their start time so that any overlapping intervals will be adjacent, then iterate through and merge those that overlap (Interval Problems | Leetcode Pattern | by Coding Aspirants | CodeX | Medium). This pattern appears in scenarios where you need to simplify or summarize intervals, such as coalescing meeting times or merging memory address ranges.

• How it Works: After sorting by start, scan the list, and if the current interval overlaps with the previous one, merge them by taking the earlier start and the later end. If not overlapping, simply add the current interval as-is (Cracking the Coding Interview: Part 5 – The Merge Intervals Pattern - DEV Community) (Interval Problems | Leetcode Pattern | by Coding Aspirants | CodeX | Medium). Overlap occurs when one interval’s start is <= the other’s end (and vice versa) (Interval Problems | Leetcode Pattern | by Coding Aspirants | CodeX | Medium).

• Common Use Cases: Merging time schedules, summarizing log time spans, merging sorted date ranges, or simplifying ranges in data (e.g. compressing intervals of busy/free time). If a problem asks for a combined set of intervals or elimination of redundancy, this pattern is a prime candidate.

• Identifying This Pattern: Clues are phrases like “merge overlapping intervals,” “output a set of non-overlapping intervals,” or any task where overlapping ranges should be treated as one. If you’re given a list of intervals and asked for a result list still in terms of intervals, likely you need to merge overlaps.

• Decision-Making Logic: Ensure intervals are sorted (if not, sort them first). Then iterate, comparing each interval to the last merged interval. If the current start is within the last interval (i.e., current.start <= lastMerged.end), they overlap and should be merged. If not, it starts after the last ended, so add it as a new interval.

• Tips & Tricks:

  • Always sort by start time first – this groups potential overlaps (Interval Problems | Leetcode Pattern | by Coding Aspirants | CodeX | Medium).

  • Use a variable or data structure to keep track of the current merged interval as you iterate.

  • Overlap check can be done via if (current.start <= last.end) (assuming inclusive intervals). Be careful with inclusive vs exclusive end intervals as problem statements vary in whether an interval like [1,2]and [2,3] counts as overlapping.

  • When merging, update the end to max(last.end, current.end). The start of the merged interval remains the same (since current.start is >= last.start after sorting).

  • A subtle trick: some prefer using if (current.start <= last.end) for overlap, while others compute overlapLen = min(last.end, current.end) - max(last.start, current.start) and check if overlapLen >= 0 (Leetcode is Easy! The Interval Pattern. | by Tim Park | Medium). Both are equivalent if intervals are sorted and one doesn’t fully envelop the other.

• Analogy: Think of each interval as a meeting in a calendar. If two meetings overlap or touch, you merge them into one longer meeting that covers from the earliest start to the latest end. Sorting by start time is like arranging meetings chronologically on your calendar before consolidating.

(image) Merging overlapping intervals. The top timeline shows original intervals (blue blocks). The first two intervals [1,3] and [2,6] overlap (highlighted in salmon), while the others do not. In the merged result (bottom timeline), overlapping intervals are combined into [1,6] (salmon), and non-overlapping ones like [8,10] and [15,18] remain separate (blue). This illustrates how sorting by start time and then merging adjacent overlaps produces a condensed set of intervals.

Example – Merging Intervals in JavaScript:
Below is a clean ES6 implementation of the merge intervals pattern. We sort the input and then iterate, merging where needed. Comments explain each step for clarity:

/**
 * Merge all overlapping intervals and return an array of the merged intervals.
 * @param {number[][]} intervals - Array of [start, end] intervals.
 * @return {number[][]} The merged list of intervals.
 */
function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];

  // 1. Sort intervals by start time (ascending order)
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [];
  // Initialize merged list with the first interval
  merged.push(intervals[0]);

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const lastMerged = merged[merged.length - 1];

    if (current[0] <= lastMerged[1]) {
      // 2. Overlap detected: current interval starts before last merged interval ends
      // Merge them by extending the end if needed
      lastMerged[1] = Math.max(lastMerged[1], current[1]);
      // We update the lastMerged in place (since merged references it), 
      // so no new interval is pushed here.
    } else {
      // 3. No overlap: this interval starts after the last merged interval ends
      // We can safely add it as a new interval in the result
      merged.push(current);
    }
  }

  return merged;
}

// Test the function with a sample input
let intervals = [[1, 3], [5, 10], [7, 15], [18, 30], [22, 25]];
console.log(mergeIntervals(intervals));
// Expected output: [ [1, 3], [5, 15], [18, 30] ]
// Explanation: [1,3] stays, [5,10] and [7,15] merged into [5,15], [18,30] and [22,25] merged into [18,30].

The code above demonstrates the key steps: sort, then merge in one pass (On log n due to sorting, and On for the merge scan). The result is a consolidated list with no overlaps.

Practice Problems (Merge Intervals Pattern): Here are 10 practice problems that rely on merging intervals – a mix of easy, medium, and hard to solidify your understanding:

1. Merge Intervals (Medium) – Given an array of intervals, merge all overlapping intervals.

2. Insert Interval (Medium) – Insert a new interval into a sorted, non-overlapping interval list and merge if necessary.

3. Intervals Intersection (Medium) – Find the intersection of two lists of intervals (output their overlapping portions).*

4. Employee Free Time (Hard) – Given schedules of multiple employees (lists of intervals), find the common free time intervals.

5. Meeting Rooms (Easy) – Determine if a person could attend all meetings given their time intervals (i.e., no overlaps).*

6. Meeting Rooms II (Medium) – Find the minimum number of conference rooms required given meeting time intervals.

7. Non-Overlapping Intervals (Medium) – Given a set of intervals, find the minimum number of intervals to remove to eliminate all overlaps. (Equivalent to maximizing non-overlapping intervals)

8. Minimum Number of Arrows to Burst Balloons (Medium) – Given balloon intervals (ranges on a number line), find the minimum number of arrows required to burst all balloons (one arrow can burst all balloons in a given point). This is essentially another formulation of merging or selecting intervals.

9. Merge K Sorted Interval Lists (Hard) – Merge multiple sorted lists of intervals into one sorted, merged list.

10. Range Sum of Sorted Subarray Sums (Hard, variation) – While not a direct interval merging problem, understanding how to merge ranges can help optimize summing ranges of subarrays.

(Problems 1–8 are classic interview questions, with slight variations reinforcing the merge pattern. Problems 9–10 are more advanced, to challenge your interval merging in a broader context.)

Insert Interval Pattern

The Insert Interval pattern builds on merging, but the input is a set of non-overlapping intervals (sorted by start), plus a new interval to insert. The task is to insert the new interval into the correct position and merge if it overlaps neighbors. Essentially, it’s a directed version of the merge pattern focusing on one new interval.

• How it Works: Iterate through the existing intervals and add them to the result, taking care to merge the new interval when appropriate:

  1. Add all intervals that end before the new interval’s start (no overlap, just keep them).

  2. Merge all intervals that overlap with the new interval (adjust the new interval’s start to the min start and its end to the max end of overlapping ones).

  3. Add all intervals that start after the new interval’s end (these come after the merged new interval in order).
     This way, the new interval is inserted at the correct sorted position and merged with any neighbors that overlap.

• Common Scenarios: This pattern applies when maintaining an interval schedule while adding new entries, such as adding a meeting to a calendar (and possibly extending an existing meeting if times overlap), or inserting a busy time into a free schedule. Another scenario is in computational geometry or memory management: adding a new range and merging it with adjacent ranges if needed.

• Identifying This Pattern: The problem description will mention a sorted, non-overlapping list and a single new interval or range to insert/insert+merge. For example, “Given a sorted list of disjoint intervals and a new interval, insert it and merge if needed.” This single-interval insertion is a giveaway.

• Decision-Making Logic: Check intervals one by one:

  • If an interval’s end is before the new interval’s start, it goes directly to output (no interaction with new interval yet).

  • When intervals start overlapping or touching the new interval (interval.start <= new.end and interval.end >= new.start), merge by updating newInterval.start = min(new.start, interval.start) and newInterval.end = max(new.end, interval.end).

  • Once all overlaps are merged, insert the new (merged) interval.

  • Then append any remaining intervals (those starting after new interval’s end).

• Tips & Tricks:

  • You can simplify by collecting all intervals that overlap with the new interval first. One trick: while iterating, find the first interval that has interval.start > newInterval.end — that’s where you stop merging and insert the new interval.

  • Be careful with edge cases: if the new interval goes at the very beginning or very end, or if it doesn’t overlap with any interval at all (it should still be placed in correct order).

  • Writing out an example on paper (with cases like “new interval comes before all,” “in the middle,” “after all,” “overlaps multiple intervals,” “does not overlap any”) can clarify the logic.

• Analogy: In a calendar of non-overlapping events, adding a new event involves finding the right time slot. If the new event overlaps existing ones, they effectively become one longer event (e.g., scheduling a meeting that extends into the next meeting’s time merges them into one continuous meeting).

Example – Inserting an Interval in JavaScript:
We’ll implement a function to insert a new interval into a sorted list, merging overlaps. The code is commented for clarity:

/**
 * Insert a new interval into a sorted array of non-overlapping intervals, merging as necessary.
 * @param {number[][]} intervals - Sorted, non-overlapping intervals [start, end].
 * @param {number[]} newInterval - The new interval [start, end] to insert.
 * @return {number[][]} Updated interval list after insertion and merging.
 */
function insertInterval(intervals, newInterval) {
  const [newStart, newEnd] = newInterval;
  const result = [];
  let i = 0;

  // 1. Add all intervals that come before the new interval (no overlap).
  while (i < intervals.length && intervals[i][1] < newStart) {
    result.push(intervals[i]);
    i++;
  }

  // 2. Merge all intervals that overlap with the new interval.
  let mergedStart = newStart;
  let mergedEnd = newEnd;
  while (i < intervals.length && intervals[i][0] <= mergedEnd) {
    // There is overlap if current interval starts before new interval ends.
    mergedStart = Math.min(mergedStart, intervals[i][0]);
    mergedEnd = Math.max(mergedEnd, intervals[i][1]);
    i++;
  }
  // After this loop, [mergedStart, mergedEnd] is the newInterval merged with any overlapping intervals.
  result.push([mergedStart, mergedEnd]);

  // 3. Add the remaining intervals that come after the new interval.
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

// Test the insertion
let intervals = [[1, 3], [6, 9]];
let newInterval = [2, 5];
console.log(insertInterval(intervals, newInterval));
// Expected output: [ [1, 5], [6, 9] ] because [1,3] and [2,5] merge into [1,5].

In this code, we handle three phases in a single pass through the list. The algorithm runs in O(n) time since we at most iterate through the list once (plus the cost of merging overlapping segments), preserving efficiency.

Practice Problems (Insert Interval Pattern): In addition to the direct insert interval problem, practice these to strengthen your skills (some overlap with merge pattern, for reinforcement):

1. Insert Interval (Medium) – Insert a new interval into sorted intervals (the classic problem above).

2. Add Bold Tag in String (Medium) – Though about strings, it can be solved by merging character index intervals for substrings to bold, essentially an interval merge after “inserting” new intervals of characters.

3. Range Module (Hard) – Design a data structure with addRange, queryRange, and removeRange. Inserting and merging intervals is central to maintaining the structure.

4. Summary Ranges (Easy) – Insert numbers into a set and output intervals of consecutive numbers (similar logic of merging contiguous intervals as numbers are inserted).

5. Interval Insertion in Circular Array (Medium) – *A variation where intervals wrap around (requires careful insertion, merging at boundaries).

6. Merge Intervals (Medium) – Revisit merging as it’s closely related – understanding merge helps insert logic.

7. Employee Free Time (Hard) – While typically solved by merging all intervals, one approach is inserting each employee’s interval one by one into a common schedule.

8. Meeting Scheduler (Medium) – Given two people’s calendars (disjoint intervals) and a new appointment duration, find a time slot to insert the meeting (requires merging and then finding a gap).

9. Partition Labels (Medium, interval-like)** – Split a string into parts so that no letter appears in more than one part. This can be solved by determining the interval of indices for each character and then merging/partitioning those intervals.

10. Minimum Interval to Include Each Query (Hard) – Given queries and intervals, for each query find the smallest interval covering it. Solving involves dynamically inserting intervals and querying – emphasizes maintaining merged intervals.

(These problems cover direct interval insertion as well as creative variations where insertion/merging logic is applicable. Problems 2, 9 involve string or array intervals rather than time, showing the concept’s versatility.)

Two-Interval Intersection Pattern

The Interval Intersection pattern involves operating on two lists of intervals to find their common intersections or related results. A classic example is finding free time slots common to two people given their busy schedules (the intersection of their busy intervals), or finding overlapping intervals between two sorted lists. This pattern typically uses a two-pointer technique because each list is sorted. By advancing pointers in tandem, you can efficiently find overlaps.

• How it Works: Given two sorted interval lists A and B, maintain two indices (i for A, j for B). At each step, check if A[i] intersects B[j].

  • An intersection exists if A[i].start <= B[j].end and B[j].start <= A[i].end (Interval Problems | Leetcode Pattern | by Coding Aspirants | CodeX | Medium). When they overlap, the overlapping interval is [max(A[i].start, B[j].start), min(A[i].end, B[j].end)]. Add that to the result.

  • Then, move the pointer that has the earlier finishing interval (whichever of A[i] or B[j] ends first) because that interval can’t produce any more intersections after its end.

  • Continue until one list is exhausted. This is O(m+n) which is efficient.

• Common Problem Structures: This pattern solves problems like finding common free time slots (intersect busy times and invert), intersecting any two sets of intervals (e.g., two sensor reading time ranges to find when both sensors were active), or merging two sorted schedules. It’s also used in variations such as counting intersections or checking if one list’s intervals are all covered by another’s.

• Identifying This Pattern: If you see two separate lists of intervals as input, often sorted, and the task is to find overlaps or common slots, it’s a strong sign for this pattern. Phrases like “between two schedules/calendars,” “for each interval in list A, find overlapping intervals in list B,” or output intersections imply this approach.

• Decision-Making Logic:

  1. Set i = 0, j = 0 at the start of each list.

  2. While i < len(A) and j < len(B):

     • Check overlap of A[i] and B[j]. If overlapping, add intersection = [max(A[i].start, B[j].start), min(A[i].end, B[j].end)] to result.

     • If A[i].end < B[j].end, it means A[i] ends earlier, so increment i (move to next interval in A). Else, increment j. (If equal, increment both or either one.)

  3. Continue until one list is done.
     This logic naturally covers all intersection cases without extra checks.

• Tips & Tricks:

  • Draw two timelines one above the other, and slide through – this helps visualize which pointer to move.

  • Don’t forget the case when one interval ends exactly when another begins: depending on whether you consider touching intervals as intersecting, min(end1, end2) == max(start1, start2) would yield a zero-length intersection which you might include or exclude based on problem specification. Typically, if intervals are closed [inclusive], touching at a point counts as intersection of a single point. If they’re half-open [start, end), touching is not an overlap. Adjust your check accordingly (>= vs >).

  • This pattern is symmetrical; it doesn’t matter which list is A or B as long as both are sorted.

• Analogy: Imagine two people walking through their day’s schedule (each with a list of busy times) and you want to find when both are free. Each person’s busy times are like blocks on a timeline. By walking through both timelines together, whenever both are busy, that overlap is time they are both unavailable (or conversely, when neither is busy, it’s a common free slot). The two-pointer method is like having one finger on each person’s schedule and moving the one that finishes earlier to find the next potential overlap.

Example – Intersecting Two Interval Lists (JavaScript):
Let’s implement a function that takes two sorted lists of intervals and returns their intersections. We’ll use the two-pointer strategy described:

/**
 * Compute the intersection of two lists of intervals.
 * @param {number[][]} A - First list of intervals [start, end], sorted by start.
 * @param {number[][]} B - Second list of intervals [start, end], sorted by start.
 * @return {number[][]} List of intersecting intervals between A and B.
 */
function intersectIntervals(A, B) {
  let i = 0, j = 0;
  const result = [];

  // Traverse both lists with two pointers
  while (i < A.length && j < B.length) {
    const [startA, endA] = A[i];
    const [startB, endB] = B[j];

    // Check if A[i] intersects B[j]
    const startMax = Math.max(startA, startB);
    const endMin = Math.min(endA, endB);
    if (startMax <= endMin) {
      // There is an overlap
      result.push([startMax, endMin]);
    }

    // Move the pointer that has the earlier finishing interval
    if (endA < endB) {
      i++;
    } else {
      j++;
    }
  }

  return result;
}

// Test the intersection function
let personA = [[1, 5], [10, 14], [16, 18]];     // busy times for person A
let personB = [[2, 6], [8, 10], [11, 20]];      // busy times for person B
console.log(intersectIntervals(personA, personB));
// Expected output: [ [2, 5], [11, 14], [16, 18] ]
// Explanation: These are the intervals where both A and B are busy at the same time.

In this code, we efficiently find overlapping segments. Notice how we increment the pointer for the interval that ends first – this ensures we don’t miss any intersections and move through the lists optimally.

Practice Problems (Interval Intersection Pattern): The following problems involve finding intersections or using the two-pointer interval approach. Practice them to recognize when two-list processing is needed:

1. Interval List Intersections (Medium) – Compute the intersection of two sorted interval lists (exactly the example we coded).

2. Employee Free Time (Hard) – Find common free intervals given each employee’s busy schedule. (Solve by merging all employees’ busy intervals then inverting to get free time, or intersecting pairwise free times.)

3. Median of Two Sorted Interval Lists (Hard, variation) – Not a standard problem, but imagine finding a median interval if you merged two sorted interval lists – understanding intersections/merging helps.

4. Conflicting Appointments (Easy) – Given two sets of appointments, determine if there is a conflict (i.e., if any interval from A intersects any from B). This is essentially checking for a non-empty intersection.

5. Shared Meeting Times (Medium) – Given two people's calendar of booked slots and a duration, find a time when both are free for at least that duration (requires intersecting their free-time intervals).*

6. Intersection of Multiple Interval Lists (Hard) – Generalize intersection to k lists: an extension where you might pairwise intersect repeatedly or use a heap to find common overlaps.

7. Merge Three Sorted Interval Lists (Medium) – Merge multiple interval lists into one – while a merge task, it can be approached by repeated two-list intersections or merges.

8. Free Time in Common (k People) (Hard) – Find a time slot when k people are all free given their busy schedules. This requires intersecting all their busy intervals (or free intervals) together.

9. Checking Sub-interval (Medium) – Given two interval lists, check if every interval in list A is covered by some interval in list B. This is solved by walking through both lists (similar to intersection logic but checking coverage instead).*

10. Align Schedules Problem (Medium) – Two machines have maintenance windows (intervals); find times they are both offline simultaneously. Intersection pattern applies.

(These problems highlight pairwise (or multiple) interval operations. Notice how often sorting + two-pointer appears. Even when more than two lists are involved, pairwise intersection/merge applied iteratively is a viable approach.)

Interval Scheduling Pattern (Selecting Non-Overlapping Intervals)

The Interval Scheduling pattern is about choosing a subset of non-overlapping intervals that optimizes some criterion, typically maximizing the number of intervals. A classic example is the Activity Selection Problem: given a set of activities each with a start and end time, select the maximum number that can be done without overlaps (Interval scheduling - Wikipedia). The greedy strategy for this (proven optimal) is to always pick the interval that finishes first (earliest end time) (Interval scheduling - Wikipedia) (Interval scheduling - Wikipedia).

• How it Works: Sort intervals by end time (earliest finishing first). Initialize count = 0 (or select none initially) and track the lastEnd of the last selected interval (initially -∞). Iterate through intervals in order of increasing end time:

  • If an interval’s start is >= lastEnd (it doesn’t overlap with the last picked interval), select it (count++ or add to result set) and update lastEnd to this interval’s end.

  • If it overlaps (start < lastEnd), skip it (drop this interval, because a shorter one is already chosen to cover that timeframe).
    By doing this, you always leave as much room as possible for the remaining intervals, thus allowing maximum intervals to fit (Interval scheduling - Wikipedia). This greedy method yields an optimal solution for the unweighted scheduling problem.

• Common Problem Structures: Any problem asking for “maximum number of non-overlapping [events/intervals/tasks]” is interval scheduling. Variations include minimizing removals to make intervals non-overlapping (which is the complement of selecting the maximum number to keep), scheduling as many talks or meetings as possible, or choosing tasks under a deadline one at a time.

• Identifying This Pattern: Look for wording like “maximum number of events you can attend,” “longest chain of intervals,” or “minimize the number of intervals to remove to avoid conflicts.” If it’s about choosing intervals without conflict (instead of merging or altering them), it’s likely an interval scheduling/selection problem.

• Decision-Making Logic:

  1. Sort by end time. This is crucial – other strategies (e.g. sorting by start or shortest interval first) do not guarantee optimal results (Interval scheduling - Wikipedia).

  2. Go through sorted intervals, using a variable lastEnd (end time of last accepted interval). Initialize lastEndto -∞ or something smaller than any start.

  3. For each interval [s, e]: if s >= lastEnd, select it (increment count or append to chosen list) and set lastEnd = e; if s < lastEnd, skip it.

  4. The count or list of selected intervals at the end is the answer.
     Because each chosen interval ends before the next one begins, they are non-overlapping. By always choosing the earliest finishing interval available, you ensure the optimality (greedy-choice property) (Interval scheduling - Wikipedia).

• Tips & Insights:

  • The greedy strategy of earliest finish is proven to maximize the count (Interval scheduling - Wikipedia). If you’re ever unsure, try small counterexamples in your head for alternative strategies; you’ll find earliest finish always works for unweighted counts.

  • Sometimes a problem might frame this as minimizing something else. For example, “minimum intervals to remove so that the rest don’t overlap” – since removing the minimum is equivalent to keeping the maximum, you solve it the same way but subtract from total.

  • If intervals have weights or values (weighted interval scheduling), the greedy approach doesn’t work; that needs dynamic programming. But for non-weighted counts or lengths, greedy works.

  • After sorting, it’s straightforward: just one pass through the data (linear time after sort). So overall complexity is dominated by sorting O(n log n). This is usually efficient even for large n.

• Analogy: Imagine you’re scheduling talks at a conference in one room. You want to fit as many talks as possible. The best strategy is to schedule the talk that finishes earliest, so you can start another one soon – as opposed to picking a long talk that blocks the room for a long time. By always picking the soonest finishing talk available, you maximize how many can fit in the day. Each time a talk ends, you pick the next one that starts after that time and finishes as early as possible.

Example – Interval Scheduling (Max Non-Overlapping Intervals) in JavaScript:
We’ll solve the “minimum intervals to remove to avoid overlap” (equivalently, maximum non-overlapping intervals to keep). The code will count the maximum set of non-conflicting intervals, then we can derive removals if needed:

/**
 * Find the maximum number of non-overlapping intervals that can be taken.
 * Also returns the minimum removals needed to eliminate overlaps.
 * @param {number[][]} intervals - Array of intervals [start, end].
 * @return {{maxCount: number, minRemovals: number}}
 */
function scheduleMaxIntervals(intervals) {
  if (intervals.length === 0) {
    return { maxCount: 0, minRemovals: 0 };
  }
  // Sort by end time (earliest end first)
  intervals.sort((a, b) => a[1] - b[1]);

  let count = 0;
  let lastEnd = -Infinity;
  for (let [start, end] of intervals) {
    if (start >= lastEnd) {
      // This interval doesn't overlap with the last selected one
      count++;
      lastEnd = end;
    } else {
      // Overlap: skip this interval (which is effectively a removal if we consider removals)
      // We don't increment count and we do NOT update lastEnd (keeping the last selected interval)
    }
  }
  const maxCount = count;
  const minRemovals = intervals.length - maxCount;
  return { maxCount, minRemovals };
}

// Test the scheduling function
let intervals = [[1, 2], [2, 4], [1, 3]];
let result = scheduleMaxIntervals(intervals);
console.log(result.maxCount, "intervals can be attended, remove", result.minRemovals);
// Expected: 2 intervals can be attended, remove 1 (e.g., attend [1,2] and [2,4], remove [1,3] which conflicts).

In the code above, maxCount is the size of the largest compatible set of intervals (non-overlapping set) (Interval scheduling - Wikipedia), and minRemovals is the complement. We sorted by end times and greedily selected non-conflicting intervals, updating lastEnd each time to ensure no overlap.

Practice Problems (Interval Scheduling Pattern): The pattern of selecting non-overlapping intervals underpins these problems:

1. Non-overlapping Intervals (Medium) – Find the minimum number of intervals to remove to eliminate all overlaps.(As above, solve by finding max non-overlapping and subtracting from total) (Interval scheduling - Wikipedia).

2. Activity Selection Problem (Easy/Medium) – Classic formulation: given start and end times, select the maximum number of activities that can be performed by a single person/machine.

3. Minimum Number of Arrows to Burst Balloons (Medium) – Analogous to interval scheduling: each balloon is an interval; an arrow shot at a point can burst all balloons overlapping that point. The minimum arrows = minimum intervals to cover all intervals, which is the complement of max non-overlapping intervals.

4. Maximum Length of Pair Chain (Medium) – Given pairs (like intervals), find the longest chain you can form where each pair can follow the previous (i.e., [a,b] can be followed by [c,d] if b < c). This is exactly interval scheduling on pairs.

5. Attend All Meetings? (Easy) – Check if one can attend all meetings (just verify no overlapping intervals). If asking for yes/no, simply sort by start and check adjacent intervals for overlap, which is a simplified version of scheduling where if maxCount < total count then you can’t attend all.

6. Maximum Events Attended (Medium) – Each event has a start and end day; you can attend one per day. This variant is a bit different (you can attend at most one event per day) but greedy by earliest end applies there too.

7. Train Scheduling (Platforms) (Medium) – Given train arrival and departure times, what’s the maximum number of trains on platform at once or minimum platforms needed? This is actually the partitioning version (meeting rooms), but sometimes they ask for maximum trains one can catch if one must catch trains serially – that becomes scheduling.

8. Course Schedule III (Hard) – You have courses with durations and deadlines, and you want to maximize how many courses you can take before their deadlines. This is a scheduling problem (though with durations and deadlines, requiring a min-heap + greedy approach). It extends the greedy idea with an extra twist.

9. Scheduling Lectures (Weighted) (Hard) – Assigning lectures to time slots to maximize attendance – if unweighted, it’s simple scheduling; if weighted by popularity, it becomes weighted interval scheduling (DP). Recognize when greedy no longer suffices.

10. Museum Guard Duty (Medium) – Given time intervals guards can work, cover the whole day with minimum guards (or maximize time covered by selected guards). Depending on exact phrasing, it could be a selection problem.

(Problems 1–5 are directly solved by the greedy approach described. Problem 3 is essentially the same logic in disguise – shoot arrows at earliest end points. Problems 6–10 are variations that either stick to greedy or test its limits (like #8 where a heap is used in combination with greedy).)

Meeting Rooms Pattern (Interval Partitioning)

The Meeting Rooms pattern focuses on allocating resources for overlapping intervals, rather than selecting intervals. A prototypical problem is Meeting Rooms II: given meeting time intervals, find the minimum number of conference rooms required so that no meetings conflict in the same room. This is an interval partitioning problem – essentially the flip side of interval scheduling. Instead of maximizing non-overlap, we want to measure/predict overlap and allocate a new “room” for each overlapping chain of intervals.

• How it Works: The maximum number of overlapping intervals at any time dictates the number of rooms (or resources) needed. To compute this, a common approach is:

  1. Sort by start times (to process meetings in chronological order).

  2. Use a min-heap (priority queue) to track current meetings by their end times – whenever a new meeting starts, compare its start with the earliest ending ongoing meeting (the top of the min-heap).

     • If the earliest ending meeting ends before the new one starts, that room gets free – pop from heap.

     • Always push the new meeting’s end time onto the heap (allocating a room, possibly reusing a freed one).

     • The heap size at any point is the number of concurrent meetings. The maximum heap size during processing is the answer (Cracking the Coding Interview: Part 5 – The Merge Intervals Pattern - DEV Community).

  3. An alternative without a heap: sweep line with two sorted lists – one of start times, one of end times. Use two pointers to traverse starts and ends to count overlaps (explained in next section). This yields the same result.

• Common Scenarios: Determining required resources: minimum number of meeting rooms, CPU cores needed to handle tasks without waiting, number of train platforms needed given train schedules, or maximum concurrent users/sessions in a log. It also covers checking if a single resource can handle all intervals (Meeting Rooms I – just check if any overlap exists). Essentially, any time you must count or allocate for overlapping intervals, this pattern is in play.

• Identifying This Pattern: Keywords like “minimum number of X to accommodate all intervals” or “maximum overlap at any time” or “how many can run in parallel” signal this pattern. For example, “What is the minimum number of classrooms required so no two classes overlap?” or “find if a single person can attend all meetings” (which is binary answer of needing >1 room or not).

• Decision-Making Logic: To determine if one resource suffices (Meeting Rooms I), sort by start and simply check if any interval starts before the previous one ends. If none do, one room suffices; if any do, more than one is needed (the answer for I is just yes/no).
  For the general “how many rooms”:

  • Sort start times and end times.

  • Take two indices i, j starting at 0 for start and end arrays, and a usedRooms = 0.

  • Iterate while i < n:

    • If start[i] < end[j]: a meeting starts before the earliest current meeting ends, so we need a new room. usedRooms++ and i++.

    • Otherwise (start[i] >= end[j]): a meeting ended before the next starts, free a room. usedRooms--(or rather, we don’t increment for a new room and just move j++ to consider that room freed). Then continue comparison.

    • Track the maximum value of usedRooms during this process – that’s the answer.

  • The heap method is conceptually similar but often easier to implement in code.

• Tips & Tricks:

  • Sorting both start and end times separately is a neat trick to avoid nested loops – you essentially line up all events in time order and count how many ongoing. Just be careful to increment pointers correctly.

  • If an interval starts exactly when another ends, this does not require a new room – one meeting ends at 10:00 and another starts at 10:00 can use the same room. To handle this, ensure that in the algorithm, if start[i] >= end[j], you treat it as no overlap (free a room). If using equal sign carefully, you won’t double-count as overlapping. In the heap approach, that means you pop the ended meeting before pushing the new one if end == start.

  • A min-heap in JavaScript isn’t built-in, but one can use an array and sort, or a library. It’s often simpler in interviews to use the two-pointer method to avoid implementing a heap from scratch.

• Visual Aid: Imagine a timeline of meetings and stacking them as we assign rooms. Each room can be seen as a horizontal lane. Overlapping meetings occupy different lanes (rooms) at the same time. The goal is to minimize lanes. The maximum number of parallel lanes needed at any point in the timeline is the answer.

(image) Allocating meeting rooms for overlapping intervals. In the figure, we have meetings labeled by their time intervals. Room 1 handles intervals [1,4] and [7,9] (sky blue), and Room 2 handles [2,5] and [8,10] (salmon). We see that between time 2 and 4, both rooms are occupied (two meetings at once, indicated by the dashed “Overlap” bracket), which is the peak overlap. The minimum number of rooms required is 2, which equals the maximum simultaneous meetings. If any new meeting started before one of the ongoing meetings ended, we’d need a third room, and so on.

Example – Minimum Meeting Rooms (JavaScript using two-pointer sweep):
We’ll implement a solution to calculate how many meeting rooms are needed. This uses the sort-and-two-pointer technique described:

/**
 * Calculate the minimum number of rooms required for all meetings.
 * @param {number[][]} intervals - Array of meeting time intervals [start, end].
 * @return {number} Minimum number of rooms needed.
 */
function minMeetingRooms(intervals) {
  if (intervals.length === 0) return 0;
  const starts = intervals.map(iv => iv[0]).sort((a, b) => a - b);
  const ends = intervals.map(iv => iv[1]).sort((a, b) => a - b);

  let rooms = 0;
  let i = 0, j = 0;
  const n = intervals.length;

  while (i < n) {
    if (starts[i] < ends[j]) {
      // A new meeting starts before an existing one ends -> need new room
      rooms++;
      i++;
    } else {
      // This meeting starts after (or exactly when) one ends -> reuse that room
      j++;
      i++;
      // (rooms stays the same or one could decrement then increment, but net effect is no change)
    }
  }

  return rooms;
}

// Test the minMeetingRooms function
let meetings = [[0, 30], [5, 10], [15, 20]];
console.log(minMeetingRooms(meetings)); 
// Expected output: 2 
// Explanation: At time 5, one meeting is ongoing (0-30), second starts (5-10) -> 2 rooms needed. By time 15, one meeting ended, back to 1 room.

In this implementation, rooms effectively tracks current simultaneous meetings, and its maximum value during the loop is the answer. We increment rooms for each new meeting start that isn’t accommodated by an ended meeting (start < end). When a meeting can reuse a freed room (start >= end), we move the end pointer forward, which allows the next start to not increase the room count. This yields the correct minimum number of rooms.

(In a heap-based approach, each new meeting start would push its end onto a min-heap, and we’d pop from the heap whenever a meeting ends before the new one starts. The size of the heap is the number of active rooms. Both methods achieve the same result and complexity.)

Practice Problems (Meeting Rooms Pattern): These problems revolve around counting overlaps or allocating resources for intervals:

1. Meeting Rooms (Easy) – Can a single room hold all meetings (i.e., is there any overlap)? (Just check for overlap; if yes, answer is false.)

2. Meeting Rooms II (Medium) – Minimum number of meeting rooms required. (As implemented above.)

3. Maximum CPU Load (Medium) – Given jobs with [start, end, CPU_load], find the maximum total CPU load at any time. Similar to Meeting Rooms II but instead of counting intervals, sum their “load” when overlapping.

4. Minimum Number of Platforms (Medium) – Given train arrival and departure times, find minimum number of platforms needed so no train waits. (Identical logic to meeting rooms.)

5. Car Pooling (Medium) – Trips are given as [numPassengers, start, end]; determine if a car with fixed capacity can handle all trips without exceeding capacity. This is essentially checking if at any time the sum of overlapping “numPassengers” exceeds capacity – an overlap counting problem with weights.

6. Parking Lot (Medium) – Given entry and exit times of cars in a parking lot, what’s the maximum number of cars simultaneously parked? (Overlap count, like meeting rooms.)

7. Airplanes in the Sky (Medium) – (LintCode classic) Given takeoff and landing times for airplanes, find the maximum number in sky at once.

8. My Calendar I (Medium) – Implement a class to book intervals without overlapping (return true if booking is possible without conflict). This requires checking for any overlap before adding – one can use a balanced BST or just maintain a list and use binary search.

9. My Calendar II (Medium/Hard) – Allow double booking but no triple booking. Count overlaps and ensure no point has 3 overlaps (requires tracking overlaps intervals specifically – more complex overlap counting).

10. The Skyline Problem (Hard) – Given building outlines (intervals with heights), output the skyline. While a different output, it uses the sweep line and a max-heap to track current overlaps of building heights. It’s a variant of counting overlaps except tracking the tallest overlap.

(Problems 1–4 map directly to meeting rooms logic. 5 and 7 are practically the same pattern with different context. Problem 6 is an easy variation. Problems 8–10 introduce more complex data handling: My Calendar requires dynamic interval management (often implemented with BST or segment tree), and Skyline involves sweep-line with a height map – an advanced use of the overlapping concept.)

Sweep Line Algorithm Pattern

The Sweep Line is a powerful pattern for interval problems, especially when counting overlapping events or combining interval sets. It involves “sweeping” a line across the timeline and tracking changes when events start or end. We convert intervals into events (typically “start” and “end” markers) and then process them in sorted order. This approach can handle counting overlaps, finding gaps, computing union lengths, and more complex queries.

• How it Works:

  1. Transform each interval [start, end] into two events: (start, +1) meaning “one interval starts here”, and (end, -1) meaning “one interval ends here”. Sometimes end is treated as (end, -1) at the end point; if using inclusive intervals, you might use (end + ε, -1) or sort end events before start events at same time to avoid counting an end as overlapping with a new start at the exact same time.

  2. Sort all events by the time coordinate (if times equal, put “end” events before “start” events to avoid counting overlap when one ends exactly as another begins).

  3. Initialize a counter = 0. Sweep through the sorted events:

     • For each event (time, type): add the type to the counter (type will be +1 for start, -1 for end).

     • The counter now represents how many intervals are currently ongoing at that time.

     • You can track the maximum value of this counter to get peak overlap, or sum up durations where counter > 0 to get total covered length, etc., depending on the problem.

  4. (Optional) If needed, as you move from one event to the next, you can compute the time difference and multiply by some value (like the counter) to accumulate weighted sums (e.g., total time with at least k overlaps, etc.).

This technique essentially converts the problem into a line traversal problem. It’s very flexible – by customizing what you track in the counter or additional variables, you can solve a variety of interval questions.

• Common Problem Structures: Counting the number of simultaneous intervals (like meeting rooms, or max CPU load – the sum version of meeting rooms), finding total length covered by intervals (union of intervals length), finding total length where at least X intervals overlap, or even computational geometry problems (like the Skyline or union of rectangles which reduces to sweep lines in two dimensions). It’s also used in more algorithmic contexts like difference arrays for range update queries. If a problem asks for a cumulative effect of many intervals or peak usage, sweep-line is a strong candidate.

• Identifying This Pattern: If it’s not just one set of intervals but requires combining many intervals or events and extracting some aggregate (max, count, total length, etc.), think of sweep line. Phrases like “at any given time,” “the total time covered,” “the maximum number of overlapping,” or “process events in chronological order” point toward this. If sorting endpoints and iterating seems natural, it’s likely a sweep line scenario.

• Decision-Making Logic:

  • Determine the events and what +1/-1 represents in context. For a simple count of overlaps, +1 for start, -1 for end is straightforward. For weighted intervals (like adding passenger counts in car pooling), +N at start, -N at end, where N is weight (number of passengers starting or leaving).

  • Sort events by position. Decide tie-break: ensure that if an interval ends exactly when another begins, you handle it correctly (usually end event first to free resource at that moment, or treat end as at a slightly later infinitesimal time).

  • Traverse and maintain a running sum (counter). Along the way, do whatever is needed: record max value achieved (for peak overlaps), or record segments where counter > 0 (for union length), etc.

  • Be mindful of data size: if there are many intervals, events list is twice that size, sorting is O(n log n). This is usually fine for up to millions of intervals.

  • Optionally use a balanced BST or heap if you need to query more complex things at each event (e.g., for the skyline you use a max-heap to track current building heights). But that’s an extension of the basic sweep line.

• Tips & Tricks:

  • Use simple data structures: often just an array of events and a counter suffice. For certain problems (like Skyline), you need a multiset or heap to track something like “current max height,” but for basic overlap counting, it’s not needed.

  • Watch out for off-by-one in end points. A common bug is double counting when one interval ends at the same time another begins. To avoid that, as noted, sort end events before start events at equal times, or treat intervals as half-open [start, end) so that an interval ending at T doesn’t count as overlapping an interval starting at T.

  • If dealing with large time coordinates (like up to 1e9), creating an array of that length for difference array is not memory efficient – the event list approach is preferred. Only store the changes.

  • Sweep line can be extended beyond time intervals (e.g., sweeping a line in 2D plane for rectangles), but that’s beyond our scope here.

• Analogy: Consider a timeline and imagine you have a broom (sweep line) that moves from left (time 0) to right (time max). When you hit the start of an interval, you pick something up (counter++). When you hit the end, you drop it (counter--). This way, you’re effectively counting how many intervals you carry at each point in time. It’s like counting how many ongoing events you have as you move through time.

(image) Sweep line counting of overlapping intervals. The chart shows a timeline with start events (green, labeled) and end events (red, labeled) for a set of intervals. As we sweep the line from time 0 to 10, we track the Active Count (purple step graph). Whenever a start is encountered, the count goes up; an end causes it to go down. In this example, the maximum active count is 2 (purple line peaks at 2), indicating the maximum overlap (which would correspond to 2 rooms needed, etc.). The sweep line method processes events in sorted order, making it easy to compute this dynamic count. We also see how at time 4, an End event brings the count down, then later more Start events bring it up again.

Example – Using Sweep Line (Car Pooling problem):
We’ll solve a problem using the sweep line: Given a list of trips [numPassengers, start, end] and a vehicle capacity, determine if the vehicle can handle the trips without exceeding capacity at any time (a LeetCode “Car Pooling” problem). This is effectively checking if at any point the sum of passengers in overlapping trips > capacity. We use sweep line to accumulate passengers:

/**
 * Car Pooling: can we pick up and drop off all passengers without exceeding capacity?
 * @param {number[][]} trips - Array of trips [numPassengers, start, end].
 * @param {number} capacity - Vehicle capacity.
 * @return {boolean} True if possible, false if capacity is exceeded at any time.
 */
function carPooling(trips, capacity) {
  const events = [];
  for (let [passengers, start, end] of trips) {
    events.push([start, passengers]);   // +passengers at start
    events.push([end, -passengers]);    // -passengers at end
  }
  // Sort events by time; if times equal, sort drop-offs (-passengers) before pickups (+passengers)
  events.sort((a, b) => {
    if (a[0] !== b[0]) return a[0] - b[0];
    return a[1] - b[1];
  });

  let currentLoad = 0;
  for (let [time, change] of events) {
    currentLoad += change;
    if (currentLoad > capacity) {
      return false; // capacity exceeded at this time
    }
  }
  return true;
}

// Test the carPooling function
let trips = [[2, 1, 5], [3, 3, 7]];  // 2 passengers from 1-5, 3 passengers from 3-7
let capacity = 4;
console.log(carPooling(trips, capacity)); 
// Expected output: false 
// Explanation: At time 3-5, total passengers = 5, which exceeds capacity 4.

In this function, we created events for pickup and drop-off, sorted them, and then iterated to check the running passenger count. We sorted drop-offs before pick-ups at the same time, so if some passengers leave at time t and others board at time t, we don’t count them concurrently (the car frees seats then fills them, never exceeding capacity at that instant). The time complexity is O(n log n) due to sorting events, and it’s very efficient for large input ranges since we only store changes instead of simulating every time unit.

Practice Problems (Sweep Line Pattern): These problems benefit from the sweep line approach or similar event-processing technique:

1. Car Pooling (Medium) – Determine if a set of passenger trips can be made without exceeding capacity at any time.(As solved above)

2. The Skyline Problem (Hard) – Given building outlines (start, end, height), draw the skyline. Use sweep line: treat building start as event +height, end as -height, use max-heap to track current height, output changes.

3. Employee Free Time (Hard) – Find common free time among employees: one approach is to collect all intervals (busy times) from all employees, mark them on a line, then find gaps where count of busy intervals drops to 0.(Sweep line or merging intervals works.)

4. Meeting Rooms II (Medium) – As discussed, can be solved via sweep line by counting concurrent meetings.

5. Maximum CPU Load (Medium) – Sum overlapping “loads” instead of count, find max load (exactly like car pooling but summing CPU usage). Uses events +load, -load.

6. Range Addition (Medium) – Apply a list of range increment operations on an array and return the result. This can be done with a difference array which is a form of sweep line: for each range [l, r] add +val at l and -val at r+1, then prefix sum.

7. Line Cover Problem (Hard) – Given numerous intervals on a line, find the length of the line covered by at least one interval (use sweep line to accumulate length where counter >0). Or length covered by at least 2 intervals, etc., by tracking counts.

8. Number of Airplanes in Sky (Medium) – Similar to Meeting Rooms II: uses events for takeoff (+1) and landing (-1) to find max airplanes concurrently in sky.

9. Burst Balloons (Range burst) (Hard, not to confuse with arrows problem) – Given many shots that can destroy balloons in a range, decide order – more of an interval DP problem, but sometimes approached with events.

10. Calendar Matching with Availability (Medium) – Two people’s calendars and working hours given (busy intervals) – find overlap in free time >= X minutes. You can mark busy intervals on a line (sweep line to merge busy times) then scan for gaps.

(Problems 1, 4, 5, 8 are direct applications of sweep line counting. Problem 2 is a famous computational geometry use of sweep line. Problem 3 and 10 mix sweep line with interval merging for free times. Problem 6 is a variant where events are array index operations. Problem 7 is about computing measure (length) of union or intersections of intervals, a classic sweep line usage. Together, they illustrate the versatility of the sweep line pattern in interval problems.)

---

By understanding these patterns – merging intervals, inserting intervals, intersecting intervals from multiple lists, selecting non-overlapping intervals optimally, allocating resources for overlapping intervals, and sweeping through events – you will have a comprehensive toolkit for tackling any interval-related problem in interviews or contests. Practice recognizing which pattern a new problem aligns with; often, a complex-looking problem simplifies greatly once the right pattern is applied. With the provided examples, tips, and practice questions, you’ll be well-prepared to master interval problems, a favorite topic in top tech company interviews. Good luck, and happy coding! (Cracking the Coding Interview: Part 5 – The Merge Intervals Pattern - DEV Community)