Skip to content

Optimal Fun Event Selection

Level: L3-L5 Topics: Greedy, Set Cover, Optimization, Scheduling

Problem Statement

Your team is planning fun events. You are given:

  • A list of people on the team.
  • A list of possible events.
  • An availability mapping: for each person and each event, the set of time slots when that person can attend that event.

An event is scheduled at one specific time slot. A person attends an event if they are available at the chosen time slot for that event.

Write a function that selects which events to hold (and at what time) to maximize total attendance (the sum of attendees across all selected events). Return the attendance score and the list of attendees for each selected event.

Background & Constraints

  • Each event can be scheduled at most once, at one of its available time slots.
  • A person can attend multiple events if they do not have time conflicts.
  • If two events are scheduled at the same time, a person available for both can only attend one (or the events are at different times and there is no conflict — clarify with interviewer).
  • The number of people, events, and time slots is small enough for exact or greedy solutions.

Examples

Input:

People: [Alice, Bob, Carol]
Events: [Bowling, Trivia, Karaoke]
Availability:
  Alice: Bowling@Mon, Trivia@Tue
  Bob:   Bowling@Mon, Bowling@Wed, Karaoke@Thu
  Carol: Trivia@Tue, Karaoke@Thu

One optimal selection:

  • Bowling on Monday: Alice, Bob attend (2 people)
  • Trivia on Tuesday: Alice, Carol attend (2 people) — no conflict with Bowling since it's a different day
  • Karaoke on Thursday: Bob, Carol attend (2 people) — no conflict with earlier events

Total attendance: 6

Hints & Common Pitfalls

  • This is related to the weighted set cover or scheduling problem.
  • A greedy approach works well: repeatedly pick the (event, time slot) pair that adds the most new attendees.
  • Be careful about double-counting: if a person's time is committed to one event, they cannot attend another at the same time.
  • For small inputs, you can enumerate all possible schedules (brute force). For larger inputs, greedy with tiebreaking is practical.
  • Think about what "total attendance" means: is it unique attendees or total person-event pairs? Clarify this.

Follow-Up Questions

  1. Manager preferences: Each person has a manager. Managers prefer that their direct reports attend events together. Add a bonus score when a manager's entire team is present at an event. How does this change the objective function?
  2. Top K events only: You can select at most K events. How does this constraint affect your approach? Does greedy still work, or do you need a different strategy?
  3. Pre-existing attendance: Some people have already committed to certain events. These are fixed. Optimize the remaining event selections around these constraints.