Katkat
Back

Maximize events attended given date ranges

SalesforceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to solve a classic greedy interval scheduling variation by using sorting and a priority queue to maximize overlapping resource utilization.

Maximize Events Attended

You are given a list of events where each event is defined by its start day and end day: events = [[start_i, end_i], ...]. You can attend at most one event per day. If you choose to attend an event, you must attend it from its start day through its end day, inclusive. Your goal is to maximize the total number of distinct events you can attend.

Implement the function maxEvents(events) that returns the maximum number of events you can attend.

Constraints

  • 1 <= events.length <= 10^5
  • 1 <= start_i <= end_i <= 10^5

Examples

Example 1: Input: events = [[1, 2], [2, 3], [3, 4]] Output: 3 Explanation: You attend event 1 on day 1, event 2 on day 2, and event 3 on day 3 (or day 4). All three can be attended.

Example 2: Input: events = [[1, 2], [1, 2], [1, 2]] Output: 1 Explanation: Even though you have three events, they all occupy the same two days. You can only attend one.

Function Signature

def maxEvents(events: List[List[int]]) -> int:

Edge Cases

  • Events with long durations that span over many days.
  • Multiple events starting on the same day.
  • Events with start and end dates that are identical.

Hints

Hint 1

Sort the events based on their start days to process them as they become available.

Hint 2

Use a min-heap to keep track of the end days of all events currently available to attend.

Hint 3

On each day, remove events from the heap that have already ended and pick the event with the earliest end date to attend.

Follow-up questions

  • What is the time complexity of your solution, and can it be improved if the range of days is significantly larger than the number of events?
  • How would the algorithm change if each event had a 'weight' or 'value' associated with it, and you wanted to maximize the total value rather than the count?
  • If you are restricted to attending at most K events, how would you modify your approach?