Largest Team with a Core Employee Overlap

Question

Form the largest team of employees such that at least one member, the core employee, has office hours that overlap the hours of every other member of the team.

As reported (translated from the poster's Chinese):

You are given the office-hour intervals of n employees, [startTime[i], endTime[i]]. You need to form a team in which at least one "core employee" exists whose working hours intersect the working hours of every other member of the team. Find the maximum number of employees the team can contain.

startTime = [2, 5, 6, 8]
endTime   = [5, 6, 10, 9]
Output: 3

The poster adds: there is a time limit, and an O(n²) solution does not pass every test.

What the example implies (our reading of it)

- Intervals that only touch count as overlapping. With the core [5, 6], the team is [2, 5], [5, 6] and [6, 10]: the core shares only the moment 5 with the first and only the moment 6 with the third.
- The other members do not have to overlap each other. [2, 5] and [6, 10] never meet, yet both are on that team. No single moment lies inside three of the intervals, and the answer is still 3.

Not reported (state your assumption)

- Input sizes, beyond "O(n²) is too slow".
- An empty list, a team of one, zero-length intervals, and whether startTime[i] ≤ endTime[i] always holds.

AceOffer · Accepted Answer

Form the largest team of employees such that at least one member, the core employee, has office hours that overlap the hours of every other member of the team.

As reported (translated from the poster's Chinese):

You are given the office-hour intervals of n employees, [startTime[i], endTime[i]]. You need to form a team in which at least one "core employee" exists whose working hours intersect the working hours of every other member of the team. Find the maximum number of employees the team can contain.

startTime = [2, 5, 6, 8]
endTime   = [5, 6, 10, 9]
Output: 3

The poster adds: there is a time limit, and an O(n²) solution does not pass every test.

What the example implies (our reading of it)

- Intervals that only touch count as overlapping. With the core [5, 6], the team is [2, 5], [5, 6] and [6, 10]: the core shares only the moment 5 with the first and only the moment 6 with the third.
- The other members do not have to overlap each other. [2, 5] and [6, 10] never meet, yet both are on that team. No single moment lies inside three of the intervals, and the answer is still 3.

Not reported (state your assumption)

- Input sizes, beyond "O(n²) is too slow".
- An empty list, a team of one, zero-length intervals, and whether startTime[i] ≤ endTime[i] always holds.

Why people fail: The poster reports that an O(n²) solution does not pass every test

Alternative approaches: Most intervals through one endpoint (sweep line) (The poster's own proposal. By our check it assumes every member shares one common moment, which the rule does not require, and it returns 2 on the posted example, where the answer is 3.); Every employee as the core, O(n²) (Correct, but the poster reports that O(n²) does not pass every test.)

What the example implies (our reading of it)

Not reported (state your assumption)

Largest Team with a Core Employee Overlap

Problem Overview

What the example implies (our reading of it)

Not reported (state your assumption)

Approach Trade-offs

What Reports Emphasize

Practice

Prepping for Citadel with friends?

More Citadel Questions

Every question in the Citadel catalog gets this depth

Approach	Notes
Most intervals through one endpoint (sweep line)	The poster's own proposal. By our check it assumes every member shares one common moment, which the rule does not require, and it returns 2 on the posted example, where the answer is 3.
Every employee as the core, O(n²)	Correct, but the poster reports that O(n²) does not pass every test.