Problem Description

You have a collection of intervals represented as a 2D array intervals, where each intervals[i] = [start_i, end_i] defines the start and end points of interval i. You're also given an integer k.

Your task is to add exactly one new interval [start_new, end_new] to the array with the following constraints:

• The length of the new interval (end_new - start_new) must be at most k
• After adding this interval, you want to minimize the number of connected groups

A connected group is a maximal set of intervals that together cover a continuous range without any gaps. When intervals overlap or touch each other, they form a single connected group.

For example:

• The intervals [[1, 2], [2, 5], [3, 3]] form one connected group because they collectively cover the range [1, 5] without gaps
• The intervals [[1, 2], [3, 4]] form two connected groups because there's a gap between 2 and 3

The goal is to strategically place your new interval (with length at most k) to connect as many existing groups as possible, thereby minimizing the total number of connected groups in the final configuration.

Return the minimum possible number of connected groups after adding exactly one new interval.

Intuition

The key insight is that we want to use our new interval to bridge gaps between existing connected groups. Since intervals within a connected group are already touching or overlapping, adding a new interval inside a group won't reduce the total number of groups.

First, we need to identify the current connected groups. We can do this by sorting the intervals and merging overlapping ones. After merging, each element in our merged array represents a distinct connected group, and the gaps between consecutive groups are where we can potentially place our new interval to connect them.

The strategic question becomes: where should we place an interval of length at most k to connect the maximum number of groups?

Consider that if we start our new interval right after some group ends (at position e where e is the end of a group), the new interval can extend up to e + k. This new interval would connect all groups that start within the range [e, e + k].

To maximize the impact, we enumerate each group's ending position as a potential starting point for our bridging interval. For each ending position e of group i, we use binary search to find the first group j whose starting position is greater than e + k. This means groups from i to j-1 can all be connected by placing our new interval starting at or near e.

The number of groups that get merged together is j - i, so the reduction in total groups is j - i - 1 (since these j - i groups become 1 group). Therefore, the resulting number of groups would be len(merged) - (j - i - 1).

By trying all possible positions and taking the minimum, we find the optimal placement for our new interval.

Learn more about Binary Search, Sorting and Sliding Window patterns.

Solution Approach

The implementation follows a three-step process: merge intervals, find optimal placement, and calculate the minimum groups.

Step 1: Sort and Merge Overlapping Intervals

First, we sort the intervals by their starting points using intervals.sort(). Then we merge overlapping intervals to identify the current connected groups:

merged = [intervals[0]]
for s, e in intervals[1:]:
    if merged[-1][1] < s:
        merged.append([s, e])
    else:
        merged[-1][1] = max(merged[-1][1], e)

For each interval [s, e], we check if it overlaps with the last interval in merged:

• If merged[-1][1] < s (the last interval's end is before the current interval's start), they don't overlap, so we add the current interval as a new group
• Otherwise, they overlap or touch, so we extend the last interval's end to max(merged[-1][1], e)

After this step, merged contains all the connected groups, and len(merged) gives us the initial number of groups.

Step 2: Find Optimal Placement Using Binary Search

We initialize ans = len(merged) as our baseline (no reduction in groups). Then for each group i with ending position e:

for i, (_, e) in enumerate(merged):
    j = bisect_left(merged, [e + k + 1, 0])
    ans = min(ans, len(merged) - (j - i - 1))

The binary search bisect_left(merged, [e + k + 1, 0]) finds the index j of the first group whose starting position is greater than or equal to e + k + 1. This means:

• Groups from index i to j-1 can all be connected by placing an interval starting at e with length k
• The new interval [e, e + k] would bridge these j - i groups into one connected group
• The reduction in total groups is j - i - 1
• The resulting number of groups is len(merged) - (j - i - 1)

Step 3: Return the Minimum

After trying all possible positions (each group's ending point), we return the minimum number of groups achievable.

The time complexity is O(n log n) for sorting plus O(n log n) for the binary searches, resulting in O(n log n) overall. The space complexity is O(n) for storing the merged intervals.

Example Walkthrough

Let's walk through the solution with a concrete example:

Input: intervals = [[1, 3], [5, 6], [8, 10], [11, 13]], k = 3

Step 1: Sort and Merge The intervals are already sorted. Since none of them overlap (there are gaps between each pair), the merged array remains the same:

• merged = [[1, 3], [5, 6], [8, 10], [11, 13]]
• Initial number of groups = 4

Step 2: Try Each Position

Now we try placing our new interval (of length ≤ 3) starting from each group's end:

Position 1: Start after group 0 ends (at position 3)

• New interval could be [3, 6] (length = 3)
• This connects groups at indices 0 and 1 (since group 1 starts at 5, which is ≤ 6)
• Binary search: bisect_left(merged, [3 + 3 + 1, 0]) = bisect_left(merged, [7, 0]) = 2
• Groups 0 to 1 get connected (2 groups become 1)
• Reduction = 2 - 0 - 1 = 1
• Result = 4 - 1 = 3 groups

Position 2: Start after group 1 ends (at position 6)

• New interval could be [6, 9] (length = 3)
• This connects groups at indices 1 and 2 (since group 2 starts at 8, which is ≤ 9)
• Binary search: bisect_left(merged, [6 + 3 + 1, 0]) = bisect_left(merged, [10, 0]) = 2
• Groups 1 to 1 get connected (just group 1 itself)
• Reduction = 2 - 1 - 1 = 0
• Result = 4 - 0 = 4 groups

Position 3: Start after group 2 ends (at position 10)

• New interval could be [10, 13] (length = 3)
• This connects groups at indices 2 and 3 (since group 3 starts at 11, which is ≤ 13)
• Binary search: bisect_left(merged, [10 + 3 + 1, 0]) = bisect_left(merged, [14, 0]) = 4
• Groups 2 to 3 get connected (2 groups become 1)
• Reduction = 4 - 2 - 1 = 1
• Result = 4 - 1 = 3 groups

Position 4: Start after group 3 ends (at position 13)

• New interval could be [13, 16] (length = 3)
• No groups start within range [13, 16]
• Binary search: bisect_left(merged, [13 + 3 + 1, 0]) = bisect_left(merged, [17, 0]) = 4
• Groups 3 to 3 get connected (just group 3 itself)
• Reduction = 4 - 3 - 1 = 0
• Result = 4 - 0 = 4 groups

Step 3: Return Minimum The minimum across all positions is 3 groups (achieved at positions 1 and 3).

Therefore, the answer is 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the following operations:

• intervals.sort(): This sorting operation takes O(n × log n) time where n is the number of intervals
• First loop to merge overlapping intervals: O(n) time as it iterates through all intervals once
• Second loop with binary search: The outer loop runs at most O(n) times (once for each merged interval), and for each iteration, bisect_left performs a binary search which takes O(log n) time. This gives us O(n × log n) in the worst case

Since O(n × log n) + O(n) + O(n × log n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space complexity comes from:

• merged list: In the worst case where no intervals overlap, this list stores all n intervals, requiring O(n) space
• The sorting operation may use O(log n) space for the recursion stack (depending on the implementation), but this is dominated by O(n)

Therefore, the overall space complexity is O(n) where n is the number of intervals.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Calculating the Reduction in Groups

The Problem: A common mistake is misunderstanding how many groups are actually being connected. When placing an interval starting at position e with length k, developers often incorrectly calculate the reduction as j - i instead of j - i - 1.

Why It Happens: The confusion arises from counting the groups being connected. If we connect groups from index i to j-1, we have j - i groups total. However, these j - i groups merge into 1 group, so the reduction is (j - i) - 1 = j - i - 1.

Example: If we have 3 groups [[1,2], [5,6], [10,11]] and our new interval connects all three, we go from 3 groups to 1 group - a reduction of 2, not 3.

Solution: Always remember that connecting n groups results in a reduction of n - 1 groups:

# Correct calculation
reduction = j - i - 1
min_groups = min(min_groups, len(merged_intervals) - reduction)

Pitfall 2: Off-by-One Error in Binary Search Target

The Problem: Using bisect_left(merged_intervals, [e + k, 0]) instead of bisect_left(merged_intervals, [e + k + 1, 0]) when finding which intervals can be connected.

Why It Happens: The new interval [e, e + k] has an endpoint at e + k. An existing interval [s, end] can be connected if s <= e + k (they touch or overlap). We want to find the first interval that CANNOT be connected, which requires s > e + k, or equivalently s >= e + k + 1.

Example: If e = 5 and k = 3, the new interval is [5, 8]. An interval starting at 8 CAN be connected (they touch), but an interval starting at 9 cannot.

Solution: Use the correct search target:

# Find first interval that CANNOT be connected
j = bisect_left(merged_intervals, [e + k + 1, 0])

Pitfall 3: Not Considering Edge Cases for Interval Placement

The Problem: Only considering placing the new interval at the end of each merged group, missing opportunities to place it at the beginning or in gaps between groups.

Why It Happens: The code only iterates through ending positions of merged intervals, which might not cover all optimal placements, especially when placing an interval at the very beginning could connect multiple groups.

Solution: Consider additional placement strategies:

# Also try placing interval before the first group
if len(merged_intervals) > 0:
    first_start = merged_intervals[0][0]
    j = bisect_left(merged_intervals, [first_start - k, 0])
    # Find how many groups can be connected from the beginning
    connected = 0
    for idx in range(len(merged_intervals)):
        if merged_intervals[idx][0] <= first_start:
            connected = idx + 1
        else:
            break
    min_groups = min(min_groups, len(merged_intervals) - connected + 1)