MediumArraySortingUnion FindUpdated Sep 2026

3893. Maximum Team Size with Overlapping Intervals

Asked at Salesforce

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given two arrays, startTime and endTime, both of length n. Employee i is available during the closed interval [startTime[i], endTime[i]].

Two employees can interact if their intervals share at least one common time point. Touching at a single endpoint counts as sharing, so [1, 4] and [4, 6] can interact.

A team is valid if at least one member of the team can interact with every other member of that team. That one member does not need to be unique. Return the largest possible size of a valid team.

Note: a team of size 1 is always valid (the single member trivially interacts with everyone else in the team, since there is nobody else).

Who can be on the same team?

startTime123012Employee 0 starts at time 1endTime456012Employee 0 ends at time 4, so its interval is [1, 4][1,4] overlaps [2,5] and [3,6]employee 0 can talk to everyone → team size 3
A valid team needs one member whose interval overlaps every other member's interval.

Constraints

  • ●1 <= n == startTime.length == endTime.length <= 10^5
  • ●0 <= startTime[i] <= endTime[i] <= 10^9

Examples

Example 1
InputstartTime = [1,2,3], endTime = [4,5,6]
Output3
WhyEmployee 0 has interval [1, 4]. It overlaps [2, 5] (shares 2, 3, 4) and [3, 6] (shares 3, 4). So employee 0 can interact with both others, making a valid team of size 3.
Example 2
InputstartTime = [2,5,8], endTime = [3,7,9]
Output1
WhyThe three intervals [2, 3], [5, 7], [8, 9] are pairwise disjoint. No employee can interact with anyone else, so the best valid team has just one member.
Example 3
InputstartTime = [3,4,6], endTime = [8,5,7]
Output3
WhyEmployee 0 has interval [3, 8]. It overlaps [4, 5] and [6, 7], so employee 0 can interact with both others and the team of size 3 is valid.

Asked At

1 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →

How to Think About It

1

Start by considering all possible pairs of intervals and checking if they overlap — this gives O(n²) brute force.

2

Sort intervals by start time so overlapping intervals group together naturally.

3

Use a sweep line approach: treat each start and end as events, sort them, and track active intervals.

4

Optimize by using a min-heap to remove intervals that end before new ones start.

5

The optimal approach is O(n log n) using sorting with sweep-line event processing.

Optimal Approach

Sort all intervals by their start time. Create a list of events where each interval start is +1 and each interval end is -1. Sort events by time (and by end before start for ties if endpoints don't count as overlap). Sweep through events, maintaining a running count of active intervals. Track the maximum count encountered during the sweep. This gives the maximum number of overlapping intervals at any point.

Sweep line over start and end events

events (time, change)(1,+1)(2,+1)(3,+1)(4,-1)(5,-1)(6,-1)Turn every interval into a start event and an end event, thensort by timeactive = 0, best = 0time 1: active = 1, best = 1time 2: active = 2, best = 2time 3: active = 3, best = 3times 4-6: active drops back downWalk the events in order and remember the peak active countbest = max(best, active)answer = 3
Each start adds one active interval, each end removes one. The largest active count is the answer.
ComplexityTime O(n log n)Space O(n)Sorting the 2n events dominates the cost; the sweep itself is a single linear pass.

What Trips People Up in Real Interviews

1

Clarify whether touching endpoints (e.g., [1,2] and [2,3]) count as overlapping.

2

Ask if intervals are guaranteed to be valid (start ≤ end) or need validation.

3

Mention that after sorting, you only need a single pass — don't suggest nested loops.

4

If asked about streaming intervals, discuss how a balanced BST or heap would maintain the sweep.

5

Discuss time complexity proactively: O(n log n) from sorting dominates the linear scan.

Solution Code

O(n log n) time
def max_team_size(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    events.sort()
    max_overlap = 0
    current = 0
    for time, change in events:
        current += change
        max_overlap = max(max_overlap, current)
    return max_overlap

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Team Size with Overlapping Intervals problem?

Given a list of intervals where each interval represents a team member's availability window, find the maximum number of team members who can form a team by selecting overlapping time windows. This problem reduces to finding the maximum overlap of intervals at any point. Consider edge cases where intervals just touch at endpoints.

How do you solve Maximum Team Size with Overlapping Intervals?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Team Size with Overlapping Intervals?

Maximum Team Size with Overlapping Intervals is asked at Salesforce. It is a medium difficulty problem.

What are common mistakes on Maximum Team Size with Overlapping Intervals?
  • Clarify whether touching endpoints (e.g., [1,2] and [2,3]) count as overlapping.
  • Ask if intervals are guaranteed to be valid (start ≤ end) or need validation.
  • Mention that after sorting, you only need a single pass — don't suggest nested loops.
  • If asked about streaming intervals, discuss how a balanced BST or heap would maintain the sweep.
  • Discuss time complexity proactively: O(n log n) from sorting dominates the linear scan.