Day 24 - Python

Problem Statement: Smart Home Event Scheduler

In a smart home automation system, a user wants to schedule multiple events such as turning on lights, adjusting the thermostat, or starting the coffee machine. Each event has a start time and end time. The system can only handle one event at a time.

You are tasked with implementing a scheduler that calculates the maximum number of non-overlapping events that can be scheduled.

Input Format:

1. An integer n — the number of events.
2. n lines follow, where each line contains two integers start and end:
   • start — the start time of the event (inclusive).
   • end — the end time of the event (exclusive).

Output Format:

• An integer representing the maximum number of non-overlapping events that can be scheduled.

Constraints:

1. $1\le n\le 10^5$
2. $0\le start<end\le 10^9$

Sample Input:

5
1 3
2 5
3 6
8 10
5 9

Sample Output:

3

Explanation:

The maximum number of non-overlapping events are:

• Event 1: [1, 3]
• Event 4: [8, 10]
• Event 2: [3, 6]

Test Cases:

Test Case 1:

Input:

4
1 2
3 4
2 3
4 5

Output:

4

Test Case 2:

Input:

3
1 5
2 6
7 8

Output:

2

Test Case 3:

Input:

6
1 4
2 3
3 5
6 7
5 8
7 9

Output:

4

Python Code:

def max_non_overlapping_events(events):

    events.sort(key=lambda x: x[1])
    
    count = 0
    last_end_time = -1
   
    for start, end in events:
        if start >= last_end_time:
            count += 1
            last_end_time = end
    
    return count

if __name__ == "__main__":
    n = int(input())
    events = []
    for _ in range(n):
        start, end = map(int, input().split())
        events.append((start, end))
    
    print(max_non_overlapping_events(events))
Insights:
Greedy Approach:
The solution uses a greedy algorithm by always selecting the event that ends the earliest, maximizing room for subsequent events.
Sorting Events:
Events are sorted by their end times using events.sort(key=lambda x: x[1]). This ensures that the scheduler prioritizes the event with the smallest end time.
Time Complexity of Sorting:
Sorting the list of events has a time complexity of $O(n\log n)$, where $n$ is the number of events.
Single Pass for Selection:
After sorting, the events are iterated through once ($O(n)$) to determine the maximum number of non-overlapping events.
Efficient Space Usage:
The algorithm operates in $O(1)$ extra space (besides the input), as it only maintains simple variables like count and last_end_time.
Comparing Start and End Times:
The condition if start >= last_end_time ensures that no two selected events overlap.
Inclusive and Exclusive Time Representation:
The use of inclusive start and exclusive end simplifies the overlap check, as events ending at time $t$ can coincide with events starting at $t$.
Handles Large Input Sizes:
The code efficiently handles up to $10^5$ events due to its $O(n\log n)$ time complexity and linear pass after sorting.
Flexible for Variations:
The code can be easily adapted to include additional event attributes, like event names, without changing the logic.
Scalability with Constraints:
The code's design ensures it works seamlessly within the constraints $0\le \text{start}<\text{end}\le 10^9$, handling large ranges of input values effectively.

Always sort your events by priority—whether it's your smart home's schedule or your Life! After all, the key to avoiding overlap is knowing when to end things before they start heating up! 😎