🦄 Unicorn Gala Scheduler

Difficulty: Advanced Tags: dp, intervals, binary-search, greedy, scheduling Series: Algorithms I

Problem

The Unicorn Gala Scheduler maximizes happiness by choosing the best events to attend. Given events with start time, end time, and reward, select non-overlapping events that maximize total reward.

Event Definition: - Each event has (start, end, reward) - Two events overlap if one starts before the other ends - Events can touch at boundaries (end time = start time of next)

Goal: Select a subset of non-overlapping events with maximum total reward.

Real-World Application

This scheduling algorithm is used in: - Meeting scheduling - maximizing productive time - Task scheduling - CPU/resource allocation - Advertisement serving - maximizing ad revenue - Job scheduling - optimizing batch processing - Conference planning - selecting talks to attend - Compiler optimization - register allocation - Cloud computing - VM scheduling for profit - Transportation - maximizing delivery value

Input

data = List[Tuple[int, int, int]]  # [(start, end, reward), ...]

Each tuple represents: - start: event start time (integer) - end: event end time (integer) - reward: value/profit of attending (integer)

Output

int  # Maximum total reward achievable

Constraints

• 1 ≤ n ≤ 200,000 events
• 0 ≤ start < end ≤ 10^9
• 1 ≤ reward ≤ 10^9
• Events can have arbitrary time ranges
• Target: O(n log n) solution

Examples

Example 1: Basic Scheduling

Input: [(1, 3, 4), (2, 5, 6), (4, 6, 3)]

Output: 7

Explanation:

Events:
A: 1-3 (reward 4)
B: 2-5 (reward 6)
C: 4-6 (reward 3)

Timeline:
    1  2  3  4  5  6
A:  |-----|
B:     |--------|
C:        |-----|

Options:
- Take A only: reward = 4
- Take B only: reward = 6
- Take C only: reward = 3
- Take A + C: reward = 4 + 3 = 7 ✓ (best)

Events A and C don't overlap (A ends at 3, C starts at 4)

Example 2: All Overlapping

Input: [(0, 10, 5), (1, 9, 6), (2, 8, 7)]

Output: 7

Explanation: All events overlap, so we can only choose one. Maximum reward is 7.

Example 3: Non-Overlapping

Input: [(1, 2, 5), (10, 20, 5), (21, 22, 5)]

Output: 15

Explanation: No events overlap, so we can take all three: 5 + 5 + 5 = 15

Example 4: Longer Chain

Input: [(1, 3, 50), (2, 5, 20), (4, 6, 30), (6, 7, 40)]

Output: 90

Explanation: - Take event 1 (1-3, reward 50) - Take event 4 (6-7, reward 40) - Total: 50 + 40 = 90

Example 5: Greedy Fails

Input: [(1, 10, 100), (2, 3, 50), (4, 5, 50), (6, 7, 50), (8, 9, 50)]

Output: 200

Explanation: - Greedy (take first): reward = 100 - Optimal (take 4 small ones): 50+50+50+50 = 200 ✓

This shows greedy doesn't work - need DP!

What You'll Learn

• Dynamic programming on sorted intervals
• Binary search for finding compatible events
• When greedy fails and DP is needed
• Handling large time ranges efficiently
• Combining sorting + DP + binary search

Why This Matters

Weighted Interval Scheduling is a classic DP problem that: - Tests multiple algorithm concepts together - Has direct real-world applications - Shows why greedy doesn't always work - Demonstrates efficient DP on sorted data

Companies that ask this: Google, Facebook, Amazon, Microsoft, Bloomberg

Starter Code

def challenge_function(data):
    """
    Find maximum reward from non-overlapping events.

    Args:
        data (List[Tuple[int, int, int]]): list of (start, end, reward) tuples

    Returns:
        int: maximum total reward achievable
    """
    # Your implementation here
    pass