3893. Maximum Team Size with Overlapping Intervals 🔒

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integer arrays startTime and endTime, both of length n.

startTime[i] represents the start time of the i-th employee.
endTime[i] represents the end time of the i-th employee.

Each employee is available during the time interval [startTime[i], endTime[i]].

Two employees i and j are able to interact if their time intervals overlap. Two intervals are considered overlapping if they share at least one common time point. For example, the intervals [1, 3] and [3, 5] overlap because they both include the time point 3.

A team is considered valid if there is at least one employee in the team who can interact with every other member of the same team. In other words, this special employee's interval must overlap with the interval of each other team member.

Your task is to return an integer denoting the maximum possible size of such a valid team.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Sorting + Interval Scan?

This problem maps to Sorting + Interval Scan through a short path in the full flowchart.

Sorting intervals and scanning processes overlapping ranges efficiently.

Open in Flowchart

Intuition

The key observation is in the definition of a valid team: there must exist at least one employee who can interact with every other member. Let's call this special employee the "center" of the team.

If we fix a particular employee as the center, then any other employee can join the team as long as their interval overlaps with the center's interval. So, for a given center employee with interval [l, r], the largest team we can build around them is simply the total number of employees whose intervals overlap with [l, r] (including the center themselves).

This transforms the problem into a much simpler one: for each employee, count how many employees overlap with their interval, and take the maximum of these counts across all employees.

Now we need an efficient way to count overlaps. Two intervals [l, r] and [s, e] overlap if and only if s <= r and e >= l. Instead of checking this condition directly against every other employee (which would be slow), we can count using the complement idea:

An interval does not overlap with [l, r] if it ends before l (that is, its end time < l), or if it starts after r (that is, its start time > r).

To count overlaps quickly, we separately sort all the start times and all the end times. Then for the center interval [l, r]:

Using the sorted endTime array, we find i, the number of employees whose end time is < l (these intervals are entirely before the center and don't overlap).
Using the sorted startTime array, we find j, the number of employees whose start time is <= r. These are all employees who could potentially overlap on the "start side".

The employees counted in j start at or before r, but some of them may have already ended before l. Those are exactly the employees counted in i. So the number of overlapping intervals is j - i.

By using binary search on the sorted arrays, each lookup is fast, and iterating over all employees gives us the final answer as the maximum overlap count found.

Solution Approach

We implement the idea using sorting combined with binary search.

Step 1: Build the interval list.

First, we combine each employee's start and end times into a single interval array intervals by zipping startTime and endTime together:

intervals = list(zip(startTime, endTime))

This lets us iterate over each employee's [l, r] interval, treating each one as a potential "center" of a team.

Step 2: Sort start times and end times separately.

We sort the startTime array and the endTime array independently:

startTime.sort()
endTime.sort()

Sorting these two arrays separately is what allows us to use binary search to count quickly. We no longer care about which start time pairs with which end time here; we only need the sorted distributions of all start times and all end times.

Step 3: For each center interval, count overlapping employees.

We iterate over every interval [l, r] in intervals and compute how many employees overlap with it:

i = bisect_right(endTime, l - 1) gives the number of employees whose end time is <= l - 1, which is the same as end time < l. These employees end strictly before the center begins, so they do not overlap.
j = bisect_right(startTime, r) gives the number of employees whose start time is <= r. These are all employees who start at or before the center ends — every employee that could possibly overlap on the start side is included here.

The difference j - i removes those who started early but ended before l, leaving exactly the count of employees whose intervals overlap with [l, r]:

i = bisect_right(endTime, l - 1)
j = bisect_right(startTime, r)
ans = max(ans, j - i)

Step 4: Track and return the maximum.

We keep a running maximum ans, updating it with each center's overlap count. After processing all employees, ans holds the size of the largest valid team:

return ans

Complexity Analysis:

Time complexity: O(n × log n). Sorting the two arrays takes O(n × log n), and for each of the n employees we perform two binary searches, each costing O(log n), for a total of O(n × log n).
Space complexity: O(n), used to store the intervals array.

Example Walkthrough

Let's use a small example with n = 4 employees:

startTime = [1, 2, 6, 4]
endTime = [3, 5, 8, 7]

So the four intervals are:

Employee	Interval
0	`[1, 3]`
1	`[2, 5]`
2	`[6, 8]`
3	`[4, 7]`

Step 1: Build the interval list.

We zip the arrays together to remember each employee's [l, r]:

intervals = [(1, 3), (2, 5), (6, 8), (4, 7)]

Step 2: Sort start times and end times separately.

startTime.sort() -> [1, 2, 4, 6]
endTime.sort()   -> [3, 5, 7, 8]

Notice these are now independent sorted distributions; we no longer track which start pairs with which end.

Step 3: For each center interval, count overlapping employees.

We treat each interval as the potential "center" and count how many employees overlap with it using two binary searches:

i = bisect_right(endTime, l - 1) → employees ending strictly before l (no overlap).
j = bisect_right(startTime, r) → employees starting at or before r.
Overlap count = j - i.

Center = (1, 3) → l = 1, r = 3

i = bisect_right([3,5,7,8], 0) = 0 → nobody ends before time 1.
j = bisect_right([1,2,4,6], 3) = 2 → start times 1 and 2 are <= 3.
Overlap = 2 - 0 = 2.

Check manually: [1,3] overlaps with [1,3] (itself) and [2,5]. ✅ Count is 2.

Center = (2, 5) → l = 2, r = 5

i = bisect_right([3,5,7,8], 1) = 0 → nobody ends before time 2.
j = bisect_right([1,2,4,6], 5) = 3 → start times 1, 2, 4 are <= 5.
Overlap = 3 - 0 = 3.

Check manually: [2,5] overlaps with [1,3], [2,5] (itself), and [4,7]. ✅ Count is 3.

Center = (6, 8) → l = 6, r = 8

i = bisect_right([3,5,7,8], 5) = 2 → end times 3 and 5 are < 6 (they finish before the center starts).
j = bisect_right([1,2,4,6], 8) = 4 → all four start times are <= 8.
Overlap = 4 - 2 = 2.

Check manually: [6,8] overlaps with [4,7] and [6,8] (itself). ✅ Count is 2.

Center = (4, 7) → l = 4, r = 7

i = bisect_right([3,5,7,8], 3) = 1 → end time 3 is < 4 (employee 0 finishes before center starts).
j = bisect_right([1,2,4,6], 7) = 4 → all four start times are <= 7.
Overlap = 4 - 1 = 3.

Check manually: [4,7] overlaps with [2,5], [6,8], and [4,7] (itself). ✅ Count is 3.

Step 4: Track and return the maximum.

Collecting all the overlap counts:

center (1,3) -> 2
center (2,5) -> 3
center (6,8) -> 2
center (4,7) -> 3

The running maximum is max(2, 3, 2, 3) = 3.

Answer: 3

This matches our intuition: using employee 1 ([2,5]) as the center, we can form a valid team of {0, 1, 3} since employee 1's interval overlaps with each of the other members'. No center yields a larger valid team, so the maximum possible team size is 3.

Solution Implementation

1from bisect import bisect_right
2
3
4class Solution:
5    def maximumTeamSize(self, startTime: list[int], endTime: list[int]) -> int:
6        # Pair up each (start, end) before sorting the standalone lists.
7        # zip materializes the tuples first, so later sorts won't affect `intervals`.
8        intervals = list(zip(startTime, endTime))
9
10        # Sort start and end times independently to enable binary search.
11        sorted_starts = sorted(startTime)
12        sorted_ends = sorted(endTime)
13
14        max_overlap = 0
15        for left, right in intervals:
16            # Count intervals that ended strictly before `left`
17            # (they do NOT overlap the current window).
18            ended_before = bisect_right(sorted_ends, left - 1)
19
20            # Count intervals that started at or before `right`
21            # (candidates that could overlap the current window).
22            started_by_right = bisect_right(sorted_starts, right)
23
24            # Difference = intervals overlapping with [left, right].
25            max_overlap = max(max_overlap, started_by_right - ended_before)
26
27        return max_overlap
28```
29
30**Notes on correctness:**
31
32- I replaced in-place `startTime.sort()` with `sorted_starts = sorted(startTime)` to avoid mutating the caller's input lists — a cleaner practice, and it makes the independence from `intervals` explicit.
33- Added the missing `from bisect import bisect_right` import so the code runs standalone.
34- The time complexity is **O(n log n)** (sorting + n binary searches), and space is **O(n)**.
35
36**Alternative perspective:** This problem is equivalent to finding the maximum number of overlapping intervals. A common alternative uses a sweep line / difference-array approach:
37
38```python3
39from collections import defaultdict
40
41
42class Solution:
43    def maximumTeamSize(self, startTime: list[int], endTime: list[int]) -> int:
44        delta = defaultdict(int)
45        for s, e in zip(startTime, endTime):
46            delta[s] += 1      # an interval starts
47            delta[e + 1] -= 1  # it ends (inclusive end, so +1)
48        current = best = 0
49        for t in sorted(delta):
50            current += delta[t]
51            best = max(best, current)
52        return best
53

1class Solution {
2    public int maximumTeamSize(int[] startTime, int[] endTime) {
3        int n = startTime.length;
4
5        // Store original (start, end) pairs before sorting the standalone arrays,
6        // because we still need to iterate over each original interval.
7        int[][] intervals = new int[n][2];
8        for (int i = 0; i < n; i++) {
9            intervals[i][0] = startTime[i];
10            intervals[i][1] = endTime[i];
11        }
12
13        // Sort start times and end times independently so we can binary search
14        // for counts of values satisfying a threshold.
15        Arrays.sort(startTime);
16        Arrays.sort(endTime);
17
18        int answer = 0;
19
20        // For each original interval [left, right], compute a candidate value.
21        for (int[] interval : intervals) {
22            int left = interval[0];
23            int right = interval[1];
24
25            // Number of end times that are <= left - 1 (i.e., strictly less than left).
26            int lowerCount = search(endTime, left - 1);
27
28            // Number of start times that are <= right.
29            int upperCount = search(startTime, right);
30
31            // The difference is the candidate; keep track of the maximum.
32            answer = Math.max(answer, upperCount - lowerCount);
33        }
34
35        return answer;
36    }
37
38    /**
39     * Upper-bound binary search.
40     * Returns the count of elements in {@code arr} that are <= {@code target},
41     * which equals the index of the first element strictly greater than target.
42     *
43     * @param arr    a sorted (ascending) array
44     * @param target the threshold value
45     * @return the first index whose element is greater than target
46     */
47    private int search(int[] arr, int target) {
48        int left = 0;
49        int right = arr.length;
50
51        while (left < right) {
52            int mid = (left + right) >>> 1;
53            if (arr[mid] > target) {
54                // mid is a valid upper bound; search the left half for a smaller one.
55                right = mid;
56            } else {
57                // arr[mid] <= target, so the answer must be to the right.
58                left = mid + 1;
59            }
60        }
61
62        return left;
63    }
64}
65

1class Solution {
2public:
3    int maximumTeamSize(vector<int>& startTime, vector<int>& endTime) {
4        int n = static_cast<int>(startTime.size());
5
6        // Store the original (start, end) pairs before sorting the arrays,
7        // because we still need each interval's boundaries as anchor points.
8        vector<pair<int, int>> intervals(n);
9        for (int i = 0; i < n; ++i) {
10            intervals[i] = {startTime[i], endTime[i]};
11        }
12
13        // Sort start times and end times independently so we can use
14        // binary search to count how many intervals satisfy a condition.
15        sort(startTime.begin(), startTime.end());
16        sort(endTime.begin(), endTime.end());
17
18        int answer = 0;
19        for (const auto& [left, right] : intervals) {
20            // Count of intervals whose end time is strictly less than `left`
21            // (i.e., intervals that have already finished before `left`).
22            int finishedBefore =
23                static_cast<int>(upper_bound(endTime.begin(), endTime.end(), left - 1) - endTime.begin());
24
25            // Count of intervals whose start time is at most `right`
26            // (i.e., intervals that have already started by `right`).
27            int startedByRight =
28                static_cast<int>(upper_bound(startTime.begin(), startTime.end(), right) - startTime.begin());
29
30            // The difference yields the number of intervals overlapping
31            // within the [left, right] window. Track the maximum.
32            answer = max(answer, startedByRight - finishedBefore);
33        }
34
35        return answer;
36    }
37};
38

1/**
2 * Finds the maximum "team size", defined here as the largest number of
3 * intervals whose start/end points fall completely within the window
4 * [l, r] of some interval taken from the input list.
5 *
6 * For each interval [l, r]:
7 *   - count how many start times are <= r        -> j
8 *   - count how many end times are <= l - 1      -> i
9 *   - the difference (j - i) represents the number of intervals that
10 *     start no later than r and end no earlier than l.
11 *
12 * @param startTime - array of interval start times
13 * @param endTime   - array of interval end times
14 * @returns the maximum team size
15 */
16function maximumTeamSize(startTime: number[], endTime: number[]): number {
17    const n: number = startTime.length;
18
19    // Build the list of original (start, end) interval pairs before sorting,
20    // so the pairing between start and end is preserved.
21    const intervals: [number, number][] = Array.from({ length: n }, (_, i) => [
22        startTime[i],
23        endTime[i],
24    ]);
25
26    // Sort start and end times independently to enable binary search.
27    startTime.sort((a, b) => a - b);
28    endTime.sort((a, b) => a - b);
29
30    let ans: number = 0;
31
32    // Evaluate every original interval as a candidate window [l, r].
33    for (const [l, r] of intervals) {
34        // Number of end times that are <= l - 1 (i.e. strictly before l).
35        const i: number = search(endTime, l - 1);
36        // Number of start times that are <= r.
37        const j: number = search(startTime, r);
38
39        // Intervals counted in j but excluded in i fit within this window.
40        ans = Math.max(ans, j - i);
41    }
42
43    return ans;
44}
45
46/**
47 * Returns the index of the first element in a sorted array that is
48 * strictly greater than x. Equivalently, this is the count of elements
49 * that are <= x (an upper-bound binary search).
50 *
51 * @param arr - a non-decreasingly sorted array
52 * @param x   - the target value to compare against
53 * @returns the upper-bound index for x
54 */
55function search(arr: number[], x: number): number {
56    let l: number = 0;
57    let r: number = arr.length;
58
59    while (l < r) {
60        const mid: number = (l + r) >> 1;
61        if (arr[mid] > x) {
62            // mid is past the target; narrow the right boundary.
63            r = mid;
64        } else {
65            // arr[mid] <= x; the answer lies to the right of mid.
66            l = mid + 1;
67        }
68    }
69
70    return l;
71}
72

Time and Space Complexity

Time Complexity: O(n × log n), where n is the number of employees.
- Building the intervals list via zip takes O(n).
- Sorting startTime and endTime each takes O(n × log n).
- The loop iterates over all n intervals, and for each interval it performs two binary searches (bisect_right), each costing O(log n). Thus the loop costs O(n × log n) in total.
- Combining these, the overall time complexity is O(n × log n).
Space Complexity: O(n), where n is the number of employees.
- The intervals list stores n tuples, requiring O(n) extra space.
- Sorting is done in place on startTime and endTime, but the sort itself may use up to O(n) auxiliary space depending on the implementation.
- Therefore, the overall space complexity is O(n).

Common Pitfalls

Pitfall: Misunderstanding the definition of a "valid team" and just counting maximum overlaps blindly.

The trap here is assuming that "maximum number of mutually overlapping intervals" is the answer. The problem only requires one special employee whose interval overlaps with every other team member — it does not require all team members to overlap with each other.

This distinction is subtle but crucial:

Pairwise-overlap (wrong interpretation): Every pair of intervals in the team must overlap.
Star-overlap (correct interpretation): There exists a single "center" interval that overlaps with all others. The non-center members are not required to overlap among themselves.

Consider these three intervals:

A: [1, 5]
B: [1, 2]
C: [4, 5]

B and C do not overlap with each other (B ends at 2, C starts at 4).
But A overlaps with both B and C.

Under the correct star-overlap definition, the whole team {A, B, C} is valid because A is the center — the answer is 3.

Under the mistaken pairwise definition, the answer would be only 2 (since no three intervals mutually overlap).

Why the provided solution is correct:

The key insight is that an employee j overlaps the center i if and only if startTime[j] <= endTime[i] AND endTime[j] >= startTime[i]. By treating each interval as a potential center and counting how many intervals overlap that center (not each other), the solution correctly implements the star-overlap definition:

ended_before     = bisect_right(sorted_ends, left - 1)   # end < left  -> no overlap
started_by_right = bisect_right(sorted_starts, right)     # start <= right
max_overlap = max(max_overlap, started_by_right - ended_before)

The count started_by_right - ended_before includes every interval that overlaps the center, regardless of whether those intervals overlap one another.

Why the sweep-line "alternative" is actually WRONG for this problem:

The sweep-line snippet presented as an alternative computes the maximum number of mutually overlapping intervals at a single point in time — that is the pairwise definition. For the example above it returns 2, not 3, because at no single time point are all three intervals simultaneously active.

# Sweep line on A:[1,5], B:[1,2], C:[4,5]
# t=1: +A +B -> 2
# t=3: -B    -> 1   (B ended at 2, so -1 at 3)
# t=4: +C    -> 2
# t=6: -A -C -> 0
# best = 2   <-- WRONG, should be 3

Fix / takeaway: Do not use the sweep-line/difference-array approach for this problem. Stick with the "every interval as center" counting method (binary search or otherwise). To verify your understanding, always test on a case where the center overlaps two members that do not overlap each other — the correct answer must include all three.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know