0841MediumArraySortingGreedyPrefix Sum

Largest Crew on Shift Together

Tracked in this browser only

Trains the technique from

LeetCode 3893Maximum Team Size with Overlapping Intervals

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A depot logs one shift per worker. Worker i clocks on at minute startTime[i] and clocks off at minute endTime[i], and is counted as present at both of those minutes and at every minute between them.

A group of workers can hold a briefing when there is some minute at which every worker in the group is present. Return the size of the largest such group.

Examples

Example 1

Input: startTime = [6, 8, 9, 20], endTime = [10, 12, 11, 25]
Output: 3

At minute 9 the workers in slots 0, 1 and 2 are all present, since 9 lies inside each of their shifts, so those three can brief together. The worker in slot 3 is not present at minute 9.

Example 2

Input: startTime = [0, 4], endTime = [4, 8]
Output: 2

The first worker is present at minute 4 because a worker counts as present at the minute they clock off, and the second is present at minute 4 because that is when they clock on.

Example 3

Input: startTime = [0, 5, 10], endTime = [4, 9, 14]
Output: 1

No minute is covered by two of these shifts, so only a single worker can be present at once.

Constraints

1 <= startTime.length <= 10^5
startTime.length == endTime.length
0 <= startTime[i] <= 10^9
0 <= endTime[i] <= 10^9
startTime[i] <= endTime[i] for every worker

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def largest_overlap_crew(startTime: list[int], endTime: list[int]) -> int:

Java

public int largestOverlapCrew(int[] startTime, int[] endTime)

The intended approach

Time O(n log n) for n workers, dominated by sorting the 2n marks.Space O(n) for the marks.

The count of workers present only changes at a clock-on or a clock-off, so the busiest minute is one of those. Turn every shift into an opening mark and a closing mark, sort the marks, and sweep them keeping a running count that rises on an opening and falls on a closing. Sorting puts an opening before a closing at the same minute, which is what makes two shifts that meet at a single minute count as overlapping there.

Pythonentry point: largest_overlap_crew

def largest_overlap_crew(startTime, endTime):
    # sweep the endpoints: an opening lifts the count, a closing drops it, and
    # openings are handled first so a shift touching another at a single instant
    # still counts as overlapping
    marks = []
    for begin, finish in zip(startTime, endTime):
        marks.append((begin, 0))
        marks.append((finish, 1))
    marks.sort()
    live = 0
    best = 0
    for _when, kind in marks:
        if kind == 0:
            live += 1
            if live > best:
                best = live
        else:
            live -= 1
    return best

The obvious version

Every clock-on and clock-off minute is a candidate. For each one, walk every shift and count how many cover that minute, keeping the largest count. Quadratic, but it reads the rule off literally.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_largest_overlap_crew(startTime, endTime):
    n = len(startTime)
    best = 0
    moments = sorted(set(startTime) | set(endTime))
    for when in moments:
        live = 0
        for i in range(n):
            if startTime[i] <= when <= endTime[i]:
                live += 1
        if live > best:
            best = live
    return best

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in