Maximize Non-Overlapping Activities
At Atlassian, managing tasks and events efficiently is crucial for productivity across products like Jira and Confluence. Imagine you're building a feature to help users optimize their personal or team schedules. This problem challenges you to identify the maximum number of activities a user can attend without any overlaps, applying a fundamental greedy approach to scheduling optimization.
Implement a function maxNonOverlappingActivities that determines the maximum number of activities that can be selected from a given list, such that no two selected activities overlap.
activities, where each element is an array [start, end] representing an activity's start and end times.activities: An array of [start, end] arrays. start and end are non-negative integers representing time, where start < end for all activities.[s1, e1] and [s2, e2] are considered non-overlapping if e1 <= s2 or e2 <= s1. This means an activity ending exactly when another begins (e.g., [1, 5] and [5, 10]) is considered non-overlapping.activities array is empty, the function should return 0.start, end) are integers.Examples
Example 1
Input:
activities = [[1, 5], [2, 3], [4, 6], [6, 8]]
Output:
3
Note:
Sorted by end time: [[2, 3], [1, 5], [4, 6], [6, 8]].
[2, 3]. Current lastEnd = 3. Count = 1.[1, 5] starts at 1, which is less than lastEnd (3). Overlaps. Skip.[4, 6] starts at 4, which is greater than or equal to lastEnd (3). Select. Current lastEnd = 6. Count = 2.[6, 8] starts at 6, which is greater than or equal to lastEnd (6). Select. Current lastEnd = 8. Count = 3.
The maximum number of non-overlapping activities is 3.Example 2
Input:
activities = [[1, 2], [2, 3], [3, 4]]
Output:
3
Note:
All activities are non-overlapping and can be selected: [1, 2], [2, 3], [3, 4].
Example 3
Input:
activities = [[1, 3], [2, 4], [3, 5]]
Output:
2
Note:
Sorted by end time: [[1, 3], [2, 4], [3, 5]].
[1, 3]. Current lastEnd = 3. Count = 1.[2, 4] starts at 2, which is less than lastEnd (3). Overlaps. Skip.[3, 5] starts at 3, which is greater than or equal to lastEnd (3). Select. Current lastEnd = 5. Count = 2.
The maximum number of non-overlapping activities is 2.Constraints
0 <= activities.length <= 10^50 <= start < end <= 10^9 for each activity [start, end].activities is not guaranteed to be sorted.Loading editor...