Efficiently Compute the Maximum Team Size from Overlapping Work Intervals (Inclusive) Using a Fenwick Tree

Learn how to find the maximum team size from overlapping schedules with inclusive boundaries using an O(N log N) Fenwick tree approach. Faster than O(N²).

When schedules overlap, teams can form. The task is simple to state: given start and end times for N employees, where intervals are inclusive on both ends, find the maximum size of a team such that everyone in that team overlaps with one specific person in the group. For the example startTime = [2,5,6,8] and endTime = [5,6,10,9], the answer must be 3.

Problem recap

We are given two arrays of equal length: start times and end times. An employee can team up with another if their working hours intersect, counting overlaps at exact boundaries as valid. The team size for a given employee is the count of employees that overlap with them, plus one for themselves. The goal is the maximum team size across all employees. In the words of the discussion, a group does not require pairwise intersection, but that all the intervals in a group intersect with one specific interval in that group.

Naïve implementation that times out

The straightforward approach checks each pair and counts overlaps. It is easy to write and reason about, but quadratic. With many employees, it will time out.

begins = [2,5,6,8]
finishes = [5,6,10,9]
m = len(begins)
best = 0
for a in range(m):
    cur = 0
    for b in range(m):
        if a == b:
            continue
        if ((begins[a] <= begins[b] <= finishes[a]) or (begins[a] <= finishes[b] <= finishes[a])):
            cur += 1
    best = max(best, cur)
print(best + 1)

This prints the correct value for the sample, but the nested loop runs in O(N²), which is not sustainable for larger inputs.

Why this is slow

The brute-force loop compares every interval with every other. Even though checking an overlap is O(1), the sheer number of comparisons dominates. To scale, we need to reduce comparisons and aggregate overlapping counts efficiently.

Optimized approach in O(N log N)

Sorting the intervals by start time unlocks a linear pass with sublinear updates. The idea is to count, for each interval, how many earlier intervals overlap it (left side), and how many later intervals overlap it (right side). Summing these gives the number of teammates for that specific interval, and the desired team size is the maximum of those sums. Both passes rely on a binary indexed tree (Fenwick tree) over compressed coordinates of all endpoints. Coordinate compression keeps the Fenwick tree compact by mapping arbitrary times to indices. During the forward pass, we maintain the multiset of previous end times. For the current start, every prior end time that is greater than or equal to this start implies an overlap on the left. During the backward pass, we maintain the multiset of upcoming start times. For the current end, every upcoming start time that is less than or equal to this end implies an overlap on the right. Careful grouping by equal start times ensures consistency when multiple intervals share the same start value.

from bisect import bisect_left as bleft
import itertools as it

def max_team(begins: list[int], finishes: list[int]):
    coords = sorted(begins + finishes)
    tree = [0] * len(coords)

    def add(pos, val):
        while pos < len(tree):
            tree[pos] += val
            pos |= pos + 1

    def pref(pos):
        acc = 0
        while pos >= 0:
            acc += tree[pos]
            pos = (pos & (pos + 1)) - 1
        return acc

    order = sorted(range(len(finishes)), key=lambda k: begins[k])
    left_cnt = [0] * len(finishes)

    for _, grp in it.groupby(order, key=lambda k: begins[k]):
        seq = list(grp)
        for idx in seq:
            left_cnt[idx] = pref(len(tree) - 1) - pref(bleft(coords, begins[idx]) - 1)
        for idx in seq:
            add(bleft(coords, finishes[idx]), 1)

    tree = [0] * len(tree)
    peak = 0

    for _, grp in it.groupby(reversed(order), key=lambda k: begins[k]):
        seq = list(grp)
        for idx in seq:
            add(bleft(coords, begins[idx]), 1)
        for idx in seq:
            total = left_cnt[idx] + pref(bleft(coords, finishes[idx]))
            if total > peak:
                peak = total

    return peak

# Example verification
print(max_team([2,5,6,8], [5,6,10,9]))  # expected: 3

This implementation runs in O(N log N). It computes, for every interval, how many intervals overlap it from the left and from the right, with inclusive boundaries respected, and returns the maximum team size as required. On the provided example, it yields 3.

Why this matters

Problems based on overlapping intervals appear in scheduling, resource allocation, log analysis, and real-time monitoring. The difference between O(N²) and O(N log N) separates prototypes from production. The Fenwick tree with coordinate compression is a practical pattern to keep in mind when you need fast prefix sums over values drawn from a large or arbitrary domain.

Takeaways

Define precisely what counts as overlap; in this case, boundaries are inclusive and a valid team hinges on intersection with a specific interval. Replace quadratic scans with sorted sweeps and indexed aggregates. A binary indexed tree over compressed coordinates offers a compact and fast way to count how many prior or future intervals contribute to the current one. With this, the maximum team size can be computed efficiently and deterministically.