Skip to main content
Talentd

Maximum Team Size with Overlapping Intervals - Solution & Explanation

MediumPremiumFree on FleetCode8 min readAsked at: Salesforce, Agoda
Practice this problem

Problem Statement

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

  • startTime[i] represents the start time of the ith employee.
  • endTime[i] represents the end time of the ith employee.

Two employees i and j can interact if their time intervals overlap. Two intervals are considered overlapping if they share at least one common time point.

A team is valid if there exists at least one employee in the team who can interact with every other member of the team.

Return an integer denoting the maximum possible size of such a team.

 

Example 1:

Input: startTime = [1,2,3], endTime = [4,5,6]

Output: 3

Explanation:

  • For i = 0 with interval [1, 4].
  • It overlaps with i = 1 having interval [2, 5] and i = 2 having interval [3, 6].
  • Thus, index 0 can interact with all other indices, so the team size is 3.

Example 2:

Input: startTime = [2,5,8], endTime = [3,7,9]

Output: 1

Explanation:

  • For i = 0, interval [2, 3] does not overlap with [5, 7] or [8, 9].
  • For i = 1, interval [5, 7] does not overlap with [2, 3] or [8, 9].
  • For i = 2, interval [8, 9] does not overlap with [2, 3] or [5, 7].
  • Thus, no index can interact with others, so the maximum team size is 1.

Example 3:

Input: startTime = [3,4,6], endTime = [8,5,7]

Output: 3

Explanation:

  • For i = 0 with interval [3, 8].
  • It overlaps with i = 1 having interval [4, 5] and i = 2 having interval [6, 7].
  • Thus, index 0 can interact with all other indices, so the team size is 3.

 

Constraints:

  • 1 <= n == startTime.length == endTime.length <= 105
  • 0 <= startTime[i] <= endTime[i] <= 109

Approach Overview

Problem Overview: You are given multiple time intervals representing when each member is available. The task is to determine the largest number of intervals that overlap at any moment. That value represents the maximum possible team size that can work together simultaneously.

Approach 1: Brute Force Interval Comparison (O(n²) time, O(1) space)

The straightforward method checks every interval against all others and counts how many overlap with it. For each interval i, iterate through the remaining intervals and test overlap conditions such as start_j ≤ end_i and end_j ≥ start_i. Track the maximum overlap count encountered. This approach is easy to reason about but becomes slow when the number of intervals grows, since every pair is compared.

Approach 2: Sweep Line with Sorted Events (O(n log n) time, O(n) space)

Transform each interval into two events: a start event (time, +1) and an end event (time, -1). Sort all events by time. Then iterate through the events while maintaining a running counter of active intervals. Each start increases the counter and each end decreases it. The maximum value reached during the scan is the largest overlapping group. This pattern is known as the sweep line technique and is commonly used in interval problems.

Approach 3: Two Sorted Arrays (Starts and Ends) (O(n log n) time, O(n) space)

Extract all start times into one array and all end times into another. Sort both arrays. Use two pointers: one iterating through starts and one through ends. When the next start time is less than or equal to the current end time, a new interval begins before the previous one ends, so increment the active team count and move the start pointer. Otherwise move the end pointer to close an interval. Track the maximum active count during the scan. This approach is conceptually similar to the sweep line but avoids building explicit event objects and relies only on sorting.

Recommended for interviews: The sweep line or two‑pointer sorted approach is what interviewers usually expect. Brute force shows you understand how overlaps work, but the optimal solution demonstrates knowledge of event ordering and efficient interval processing. Both optimal approaches run in O(n log n) due to sorting and handle large datasets comfortably.

Solution

We first combine each employee's start and end times into an interval array, intervals, and sort all start times and end times separately.

For each employee i, we use binary search to compute how many employees have end times not earlier than employee i's start time, and how many employees have start times not later than employee i's end time. The difference between these two counts is the number of employees whose intervals overlap with employee i. We iterate through all employees, compute the overlap count for each one, and take the maximum as the answer.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the number of employees.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Interval ComparisonO(n²)O(1)Small input sizes or when explaining the overlap concept first
Sweep Line with Event SortingO(n log n)O(n)General case; standard solution for maximum overlapping intervals
Two Pointers on Sorted Start/End ArraysO(n log n)O(n)Cleaner implementation when only counts of overlaps are required

Frequently Asked Questions

Is Maximum Team Size with Overlapping Intervals easy or hard?
The problem is generally classified as medium difficulty. Identifying that overlapping intervals correspond to counting active events is the key insight. Once you recognize the sweep line pattern, the implementation becomes straightforward.
Maximum Team Size with Overlapping Intervals Python/Java solution
Most implementations sort interval boundaries and perform a linear scan. In Python, lists and built-in sorting are enough to implement the sweep line or two-pointer technique. Java solutions typically use arrays or ArrayList with Collections.sort to process event points.
How to solve Maximum Team Size with Overlapping Intervals in O(n)?
Pure O(n) time is only possible when the timeline range is small enough to use a difference array or prefix sum technique. Mark +1 at each start and −1 after each end, then compute a running prefix sum to track active intervals. In general interview settings where times are arbitrary, sorting-based O(n log n) sweep line solutions are expected.
What is the best approach for Maximum Team Size with Overlapping Intervals?
The sweep line technique is the most common solution. Convert every interval into start and end events, sort them, and scan while maintaining the number of active intervals. The maximum active count during the scan represents the largest possible team working simultaneously. This runs in O(n log n) time due to sorting.
Is Maximum Team Size with Overlapping Intervals asked at Google/Amazon/Meta?
Interval overlap and sweep line problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. Variants include meeting rooms, maximum concurrent users, and resource allocation problems. The core concept remains counting simultaneous intervals efficiently.
What data structure is used in Maximum Team Size with Overlapping Intervals?
Typical implementations rely on arrays or lists combined with sorting. Some variants use priority queues or heaps when intervals must be actively tracked. For the classic maximum overlap calculation, a sorted event list or two sorted arrays of start and end times is sufficient.
What is the time complexity of Maximum Team Size with Overlapping Intervals?
The optimal solution runs in O(n log n) time and O(n) space. Sorting either event points or the start/end arrays dominates the complexity. A naive pairwise comparison approach exists but takes O(n²) time and does not scale well.

Ready to solve this problem?

Practice Maximum Team Size with Overlapping Intervals with our built-in code editor and test cases.

Practice on FleetCode