This post is completed by 2 users

  • 0
 Add to List
Hard

553. Minimize Scheduling Headaches: Clone Yourself for Overlapping Events

Problem Statement

You have a calendar with n events, each defined by a start time and a finish time. Some events may overlap, making it impossible for a single person to attend all of them. To ensure that every event is attended, you need to create k clones of yourself. Each clone can attend a subset of non-overlapping events. The objective is to minimize the number of clones required to cover all events.

Example 1:

Events: [(1, 3),(2, 5),(4, 6)]
Output: 2 
Clone 1 - (1, 3) and (4, 6).
Clone 2 - (2, 5)

Example 2:

Events: [(1,4),(2,3),(3,5),(7,9)]
Output: 2
Clone 1 - (1, 4)(7,9)
Clone 2 - (2, 3)(3,5)

Approach: Greedy solution

  • Sorting Events:
    • This sorts the events based on their start times, ensuring we process them in chronological order.
  • Min Heap Initialization:
    • The min heap is used to keep track of the end times of clones, always allowing access to the clone that finishes the earliest.
  • Processing Events:
    • The for-loop iterates over each event and determines if the earliest available clone (the one with the smallest end time) can attend the event.
    • If the clone can attend, its end time is updated.
    • If no clone can attend, a new clone is created and added to the queue.
  • Counting Clones:
    • After processing all events, the size of the priority queue indicates the minimum number of clones needed.

Complete Code:

 

Output:

Minimum clones required: 4

Related Problems: