Interval List Intersections

🎯

Interval List Intersections

mediumINTERVALSFacebookAmazonGoogle

Imagine two friends each have their own schedule of busy time slots, and you want to find all the times when both are busy simultaneously.

💡 This problem involves understanding how to find overlapping intervals between two lists. Beginners often struggle because it requires careful pointer movement and interval comparisons, which can be tricky without a clear approach.

📋

Problem Statement

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. Each intersection is a closed interval that represents the overlapping time between intervals from the two lists.

1 ≤ number of intervals in each list ≤ 10^5Intervals are sorted by start time and do not overlap within the same listInterval start and end values are integers within a valid range

💡

Example

Input"A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]"

Output[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

We find all overlapping intervals by comparing intervals from A and B and collecting their intersections.

• One or both lists are empty → output is empty list
• Intervals that touch at a single point (e.g., [1,2] and [2,3]) → intersection is that single point [2,2]
• One list has intervals completely before or after the other list → no intersections
• Intervals with the same start and end (single-point intervals) → handled correctly

⚠️

Common Mistakes

Not advancing pointers correctly

Infinite loop or missed intersections

✅ Always advance the pointer with the smaller interval end

Incorrect overlap condition (using < instead of <=)

Misses intersections where intervals touch at a point

✅ Use start <= end to include touching intervals

Assuming intervals within the same list can overlap

Incorrect results or complexity assumptions

✅ Remember problem states intervals are disjoint within each list

Not handling empty input lists

Runtime errors or incorrect output

✅ Check for empty lists before processing

Appending intervals without checking overlap

Incorrect intervals in output

✅ Check if start <= end before appending

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by checking every possible pair of intervals, which helps understand the problem deeply before optimizing.

Intuition

Compare every interval in list A with every interval in list B to find overlaps. If intervals overlap, record the intersection.

Algorithm

1. Initialize an empty result list.
2. For each interval in list A, iterate through all intervals in list B.
3. Check if the two intervals overlap by comparing their start and end points.
4. If they overlap, compute the intersection and add it to the result list.

💡 Nested loops make it easy to understand but inefficient; it's a direct translation of the problem statement.

</>

Code

from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    result = []
    for i in range(len(A)):
        for j in range(len(B)):
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            if start <= end:
                result.append([start, end])
    return result

# Driver code
if __name__ == '__main__':
    A = [[0,2],[5,10],[13,23],[24,25]]
    B = [[1,5],[8,12],[15,24],[25,26]]
    print(intervalIntersection(A, B))

Line Notes

result = []Initialize list to store intersections

for i in range(len(A))Outer loop iterates over intervals in A

for j in range(len(B))Inner loop iterates over intervals in B

start = max(A[i][0], B[j][0])Find the later start time between two intervals

end = min(A[i][1], B[j][1])Find the earlier end time between two intervals

if start <= endCheck if intervals overlap

result.append([start, end])Add the overlapping interval to result

import java.util.*;

public class IntervalIntersection {
    public static List<int[]> intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int start = Math.max(A[i][0], B[j][0]);
                int end = Math.min(A[i][1], B[j][1]);
                if (start <= end) {
                    result.add(new int[]{start, end});
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] A = {{0,2},{5,10},{13,23},{24,25}};
        int[][] B = {{1,5},{8,12},{15,24},{25,26}};
        List<int[]> res = intervalIntersection(A, B);
        for (int[] interval : res) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}

Line Notes

List<int[]> result = new ArrayList<>();Create list to store intersections

for (int i = 0; i < A.length; i++)Outer loop over intervals in A

for (int j = 0; j < B.length; j++)Inner loop over intervals in B

int start = Math.max(A[i][0], B[j][0]);Later start time between intervals

int end = Math.min(A[i][1], B[j][1]);Earlier end time between intervals

if (start <= end)Check if intervals overlap

result.add(new int[]{start, end});Add intersection to result

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> result;
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            int start = max(A[i][0], B[j][0]);
            int end = min(A[i][1], B[j][1]);
            if (start <= end) {
                result.push_back({start, end});
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,26}};
    vector<vector<int>> res = intervalIntersection(A, B);
    for (auto &interval : res) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}

Line Notes

vector<vector<int>> result;Initialize vector to store intersections

for (int i = 0; i < A.size(); i++)Outer loop over intervals in A

for (int j = 0; j < B.size(); j++)Inner loop over intervals in B

int start = max(A[i][0], B[j][0]);Later start time between intervals

int end = min(A[i][1], B[j][1]);Earlier end time between intervals

if (start <= end)Check if intervals overlap

result.push_back({start, end});Add intersection to result

function intervalIntersection(A, B) {
    const result = [];
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B.length; j++) {
            const start = Math.max(A[i][0], B[j][0]);
            const end = Math.min(A[i][1], B[j][1]);
            if (start <= end) {
                result.push([start, end]);
            }
        }
    }
    return result;
}

// Test
const A = [[0,2],[5,10],[13,23],[24,25]];
const B = [[1,5],[8,12],[15,24],[25,26]];
console.log(intervalIntersection(A, B));

Line Notes

const result = []Initialize array to store intersections

for (let i = 0; i < A.length; i++)Outer loop over intervals in A

for (let j = 0; j < B.length; j++)Inner loop over intervals in B

const start = Math.max(A[i][0], B[j][0])Later start time between intervals

const end = Math.min(A[i][1], B[j][1])Earlier end time between intervals

if (start <= end)Check if intervals overlap

result.push([start, end])Add intersection to result

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We compare each interval in A with each interval in B, resulting in m*n comparisons. The result can be up to m*n in worst case.

💡 For 100 intervals in each list, this means 10,000 comparisons, which is inefficient for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠

Two Pointers Approach

💡 This approach improves efficiency by leveraging the sorted and disjoint nature of the interval lists, using two pointers to traverse both lists simultaneously.

Intuition

Since both lists are sorted and intervals do not overlap within the same list, we can use two pointers to iterate through both lists and find intersections by advancing the pointer with the smaller interval end.

Algorithm

1. Initialize two pointers i and j at 0 for lists A and B respectively.
2. While both pointers are within their list bounds, compare intervals A[i] and B[j].
3. Find the intersection by taking max of starts and min of ends; if they overlap, add to result.
4. Advance the pointer whose interval ends first to find new potential intersections.

💡 This approach avoids unnecessary comparisons by moving pointers smartly based on interval ends.

</>

Code

from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])
        if start <= end:
            result.append([start, end])
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

# Driver code
if __name__ == '__main__':
    A = [[0,2],[5,10],[13,23],[24,25]]
    B = [[1,5],[8,12],[15,24],[25,26]]
    print(intervalIntersection(A, B))

Line Notes

i, j = 0, 0Initialize pointers for both lists

while i < len(A) and j < len(B)Loop until one list is exhausted

start = max(A[i][0], B[j][0])Later start time between current intervals

end = min(A[i][1], B[j][1])Earlier end time between current intervals

if start <= endCheck if intervals overlap

result.append([start, end])Add intersection to result

if A[i][1] < B[j][1]Advance pointer with smaller interval end

i += 1Move pointer i forward

elseOtherwise, move pointer j forward

j += 1Move pointer j forward

import java.util.*;

public class IntervalIntersection {
    public static List<int[]> intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            int start = Math.max(A[i][0], B[j][0]);
            int end = Math.min(A[i][1], B[j][1]);
            if (start <= end) {
                result.add(new int[]{start, end});
            }
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] A = {{0,2},{5,10},{13,23},{24,25}};
        int[][] B = {{1,5},{8,12},{15,24},{25,26}};
        List<int[]> res = intervalIntersection(A, B);
        for (int[] interval : res) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}

Line Notes

int i = 0, j = 0;Initialize pointers for both lists

while (i < A.length && j < B.length)Loop until one list is exhausted

int start = Math.max(A[i][0], B[j][0]);Later start time between current intervals

int end = Math.min(A[i][1], B[j][1]);Earlier end time between current intervals

if (start <= end)Check if intervals overlap

result.add(new int[]{start, end});Add intersection to result

if (A[i][1] < B[j][1])Advance pointer with smaller interval end

i++;Move pointer i forward

elseOtherwise, move pointer j forward

j++;Move pointer j forward

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> result;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size()) {
        int start = max(A[i][0], B[j][0]);
        int end = min(A[i][1], B[j][1]);
        if (start <= end) {
            result.push_back({start, end});
        }
        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,26}};
    vector<vector<int>> res = intervalIntersection(A, B);
    for (auto &interval : res) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}

Line Notes

int i = 0, j = 0;Initialize pointers for both lists

while (i < A.size() && j < B.size())Loop until one list is exhausted

int start = max(A[i][0], B[j][0]);Later start time between current intervals

int end = min(A[i][1], B[j][1]);Earlier end time between current intervals

if (start <= end)Check if intervals overlap

result.push_back({start, end});Add intersection to result

if (A[i][1] < B[j][1])Advance pointer with smaller interval end

i++;Move pointer i forward

elseOtherwise, move pointer j forward

j++;Move pointer j forward

function intervalIntersection(A, B) {
    let i = 0, j = 0;
    const result = [];
    while (i < A.length && j < B.length) {
        const start = Math.max(A[i][0], B[j][0]);
        const end = Math.min(A[i][1], B[j][1]);
        if (start <= end) {
            result.push([start, end]);
        }
        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

// Test
const A = [[0,2],[5,10],[13,23],[24,25]];
const B = [[1,5],[8,12],[15,24],[25,26]];
console.log(intervalIntersection(A, B));

Line Notes

let i = 0, j = 0;Initialize pointers for both lists

while (i < A.length && j < B.length)Loop until one list is exhausted

const start = Math.max(A[i][0], B[j][0])Later start time between current intervals

const end = Math.min(A[i][1], B[j][1])Earlier end time between current intervals

if (start <= end)Check if intervals overlap

result.push([start, end])Add intersection to result

if (A[i][1] < B[j][1])Advance pointer with smaller interval end

i++Move pointer i forward

elseOtherwise, move pointer j forward

j++Move pointer j forward

⏱

Complexity

TimeO(m + n)

SpaceO(m + n)

Each interval is visited at most once by the pointers, resulting in linear time relative to input size.

💡 For 100 intervals in each list, this means about 200 operations, which is efficient for large inputs.

Interview Verdict: Accepted / Optimal for this problem

This approach is efficient and the best practical solution for this problem.

🧠

Two Pointers with Early Skipping

💡 This approach refines the two pointers method by explicitly skipping intervals that cannot overlap, improving clarity and sometimes performance.

Intuition

If one interval ends before the other starts, we can skip it immediately, reducing unnecessary comparisons.

Algorithm

1. Initialize two pointers i and j at 0.
2. While both pointers are valid, check if intervals A[i] and B[j] overlap.
3. If they overlap, add the intersection to the result.
4. If A[i] ends before B[j] starts, increment i to skip A[i].
5. Else if B[j] ends before A[i] starts, increment j to skip B[j].
6. Otherwise, advance the pointer with the smaller end to find new overlaps.

💡 This approach explicitly handles non-overlapping cases first, making the logic clearer and potentially faster.

</>

Code

from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] < B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result

# Driver code
if __name__ == '__main__':
    A = [[0,2],[5,10],[13,23],[24,25]]
    B = [[1,5],[8,12],[15,24],[25,26]]
    print(intervalIntersection(A, B))

Line Notes

if A[i][1] < B[j][0]Skip A[i] if it ends before B[j] starts

i += 1Move pointer i forward

elif B[j][1] < A[i][0]Skip B[j] if it ends before A[i] starts

j += 1Move pointer j forward

elseOtherwise, move pointer j forward

start = max(A[i][0], B[j][0])Later start time between intervals

end = min(A[i][1], B[j][1])Earlier end time between intervals

result.append([start, end])Add intersection to result

if A[i][1] < B[j][1]Advance pointer with smaller interval end

import java.util.*;

public class IntervalIntersection {
    public static List<int[]> intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            if (A[i][1] < B[j][0]) {
                i++;
            } else if (B[j][1] < A[i][0]) {
                j++;
            } else {
                int start = Math.max(A[i][0], B[j][0]);
                int end = Math.min(A[i][1], B[j][1]);
                result.add(new int[]{start, end});
                if (A[i][1] < B[j][1]) {
                    i++;
                } else {
                    j++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] A = {{0,2},{5,10},{13,23},{24,25}};
        int[][] B = {{1,5},{8,12},{15,24},{25,26}};
        List<int[]> res = intervalIntersection(A, B);
        for (int[] interval : res) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}

Line Notes

if (A[i][1] < B[j][0])Skip A[i] if it ends before B[j] starts

i++;Move pointer i forward

else if (B[j][1] < A[i][0])Skip B[j] if it ends before A[i] starts

j++;Move pointer j forward

elseOtherwise, move pointer j forward

int start = Math.max(A[i][0], B[j][0]);Later start time between intervals

int end = Math.min(A[i][1], B[j][1]);Earlier end time between intervals

result.add(new int[]{start, end});Add intersection to result

if (A[i][1] < B[j][1])Advance pointer with smaller interval end

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> result;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size()) {
        if (A[i][1] < B[j][0]) {
            i++;
        } else if (B[j][1] < A[i][0]) {
            j++;
        } else {
            int start = max(A[i][0], B[j][0]);
            int end = min(A[i][1], B[j][1]);
            result.push_back({start, end});
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,26}};
    vector<vector<int>> res = intervalIntersection(A, B);
    for (auto &interval : res) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}

Line Notes

if (A[i][1] < B[j][0])Skip A[i] if it ends before B[j] starts

i++;Move pointer i forward

else if (B[j][1] < A[i][0])Skip B[j] if it ends before A[i] starts

j++;Move pointer j forward

elseOtherwise, move pointer j forward

int start = max(A[i][0], B[j][0]);Later start time between intervals

int end = min(A[i][1], B[j][1]);Earlier end time between intervals

result.push_back({start, end});Add intersection to result

if (A[i][1] < B[j][1])Advance pointer with smaller interval end

function intervalIntersection(A, B) {
    let i = 0, j = 0;
    const result = [];
    while (i < A.length && j < B.length) {
        if (A[i][1] < B[j][0]) {
            i++;
        } else if (B[j][1] < A[i][0]) {
            j++;
        } else {
            const start = Math.max(A[i][0], B[j][0]);
            const end = Math.min(A[i][1], B[j][1]);
            result.push([start, end]);
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }
    }
    return result;
}

// Test
const A = [[0,2],[5,10],[13,23],[24,25]];
const B = [[1,5],[8,12],[15,24],[25,26]];
console.log(intervalIntersection(A, B));

Line Notes

if (A[i][1] < B[j][0])Skip A[i] if it ends before B[j] starts

i++Move pointer i forward

else if (B[j][1] < A[i][0])Skip B[j] if it ends before A[i] starts

j++Move pointer j forward

elseOtherwise, move pointer j forward

const start = Math.max(A[i][0], B[j][0])Later start time between intervals

const end = Math.min(A[i][1], B[j][1])Earlier end time between intervals

result.push([start, end])Add intersection to result

if (A[i][1] < B[j][1])Advance pointer with smaller interval end

⏱

Complexity

TimeO(m + n)

SpaceO(m + n)

Each interval is visited at most once, skipping non-overlapping intervals early reduces unnecessary checks.

💡 This approach is as efficient as the previous but can be easier to understand and slightly faster in practice.

Interview Verdict: Accepted / Optimal and clear

This approach is recommended for clarity and performance in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The two pointers approach (Approach 2 or 3) is the best choice for interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m*n)	O(m*n)	No	N/A	Mention only - never code
2. Two Pointers	O(m + n)	O(m + n)	No	N/A	Code this approach
3. Two Pointers with Early Skipping	O(m + n)	O(m + n)	No	N/A	Code this approach for clarity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare for common edge cases and follow-ups.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the two pointers approach and why it is efficient.Step 4: Code the two pointers solution carefully.Step 5: Test with examples and edge cases.Step 6: Discuss possible follow-ups or optimizations.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to handle interval comparisons, use two pointers effectively, and write clean, bug-free code.

Common Follow-ups

• What if intervals are not sorted? → Sort first, then apply two pointers.
• How to handle open intervals? → Adjust comparison logic accordingly.
• Can this be extended to k lists? → Use a heap or pairwise intersection.
• What if intervals overlap within the same list? → Merge intervals first.

💡 These follow-ups test your adaptability and deeper understanding of interval problems.

🔍

Pattern Recognition

When to Use

1) You have two lists of intervals, 2) Both lists are sorted and disjoint internally, 3) You need to find overlapping intervals, 4) Efficient linear time is required.

Signature Phrases

interval list intersectionsfind overlapping intervalstwo sorted lists of intervals

NOT This Pattern When

Problems involving intervals but requiring DP or scheduling optimization are different patterns.

Similar Problems

Merge Intervals - merging overlapping intervals in one listInsert Interval - inserting and merging a new intervalNon-overlapping Intervals - removing overlaps to minimize intervals

Practice

1. You are given a list of intervals and a list of queries. For each query, you need to find the length of the smallest interval that contains that query point. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach by always picking the interval with the earliest start time that covers the query.

B. Use dynamic programming to build a table of minimum intervals covering each possible query point.

C. Sort intervals by their length and use binary search combined with interval coverage checks for each query.

D. For each query, iterate over all intervals and pick the smallest covering interval (brute force).

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the smallest interval covering each query, which suggests sorting intervals by length to efficiently check coverage.

2. Step 2: Identify optimal approach

   Sorting intervals by length and using binary search to limit checks to intervals up to a certain length allows efficient coverage verification for each query.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search on sorted intervals by length is optimal and avoids brute force [OK]

Hint: Sort intervals by length and binary search coverage [OK]

Common Mistakes:

• Assuming greedy earliest start time always works
• Trying DP over all points is inefficient
• Using brute force for large inputs

2. Examine the following code snippet intended to compute the minimum number of platforms required. Identify the line containing the subtle bug that can cause incorrect platform count when a train departs and another arrives at the same time.

medium

A. Line 6: Appending departure events with -1 instead of 1

B. Line 10: Not resetting platforms_needed before loop

C. Line 8: Sorting events with arrival before departure on tie

D. Line 12: Not updating max_platforms after each event

Solution

1. Step 1: Understand event sorting importance

   When arrival and departure times are equal, departures must be processed before arrivals to free platforms.

2. Step 2: Identify sorting key bug

   The code sorts with arrival (1) before departure (-1) on tie, causing overcounting platforms.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Departure before arrival on tie avoids overcounting [OK]

Hint: Departure events must come before arrival on tie [OK]

Common Mistakes:

• Sorting arrival before departure on tie
• Forgetting to update max_platforms
• Incorrect event type values

3. Suppose the problem changes: intervals can be reused infinitely many times, and you want to count how many intervals contain each point considering unlimited reuse (e.g., intervals repeat periodically). Which modification to the line sweep approach correctly handles this scenario?

hard

A. No change needed; line sweep already counts intervals correctly regardless of reuse.

B. Preprocess intervals to merge overlapping intervals into one, then run line sweep once.

C. Use a segment tree or binary indexed tree to handle repeated intervals efficiently instead of line sweep.

D. Modify events to include multiple copies of intervals explicitly and run line sweep on expanded events.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means intervals repeat periodically, so naive line sweep with explicit events cannot handle infinite copies.

2. Step 2: Recognize data structure need

   Segment trees or binary indexed trees can efficiently query counts over ranges and handle repeated intervals without enumerating all copies.

3. Step 3: Why other options fail

   No change (A) ignores infinite reuse; merging (B) loses count detail; explicit expansion (D) is infeasible for infinite repeats.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Segment trees handle range queries with repeated intervals efficiently [OK]

Hint: Infinite reuse requires data structures, not event enumeration [OK]

Common Mistakes:

• Assuming line sweep handles infinite repeats
• Trying to expand events explicitly
• Merging intervals loses count accuracy

4. Suppose the problem is extended so that numbers can be added multiple times (duplicates allowed), and the intervals must reflect the count of each number (e.g., intervals store counts of coverage). Which modification to the optimal balanced tree approach is necessary to handle this correctly?

hard

A. Augment intervals with counts and update counts on insertion; merge intervals only if counts allow.

B. Keep the current approach but ignore duplicates since intervals are disjoint sets.

C. Use a brute force approach storing all numbers and recomputing intervals with counts on each query.

D. Replace balanced tree with a hash map keyed by number to track counts and intervals separately.

Solution

1. Step 1: Understand the impact of duplicates

   Intervals must now track counts, so simple presence is insufficient.

2. Step 2: Modify data structure

   Intervals should store counts per interval or per number; merging must consider counts to avoid losing duplicates.

3. Step 3: Evaluate options

   Ignoring duplicates (B) breaks correctness. Brute force (C) is inefficient. Hash map (D) loses interval ordering benefits. Augmenting intervals with counts (A) preserves efficiency and correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Counting duplicates requires augmenting intervals [OK]

Hint: Track counts in intervals to handle duplicates correctly [OK]

Common Mistakes:

• Ignoring duplicates
• Using brute force for counts
• Losing interval order with hash maps

5. Suppose the meeting intervals can be reused multiple times (i.e., a meeting can be attended multiple times if no overlaps occur). Which modification to the algorithm is necessary to correctly determine if a person can attend all meetings without overlap?

hard

A. Sort intervals by end time and greedily select intervals to maximize non-overlapping meetings.

B. No change needed; the original algorithm already handles reuse correctly.

C. Use a frequency map to count how many times each interval appears and check overlaps accordingly.

D. Sort intervals by start time and check overlaps as before, but also track counts of repeated intervals.

Solution

1. Step 1: Understand reuse scenario

   Reusing intervals means attending multiple instances of the same meeting, so we want to maximize the number of non-overlapping meetings.

2. Step 2: Identify correct approach

   Sorting by end time and greedily selecting earliest finishing meetings maximizes non-overlapping intervals, handling reuse correctly.

3. Step 3: Why other options fail

   Original algorithm only checks if all intervals can be attended once; frequency maps or tracking counts do not solve scheduling conflicts optimally.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Greedy by end time is classic interval scheduling for maximum non-overlapping intervals [OK]

Hint: Reuse requires interval scheduling by end time [OK]

Common Mistakes:

• Assuming original overlap check suffices for reuse
• Trying to track counts without scheduling logic