Frontend School

Maximize Non-Overlapping Activities

DSA
easy

Maximize Non-Overlapping Activities

Easy
Greedy
Arrays
Sorting

Overview

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.

What you need to do / Task

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.

  1. The function will receive an array, activities, where each element is an array [start, end] representing an activity's start and end times.
  2. Your task is to return the largest possible count of activities that can be attended without any time conflicts.

Input & output

  • activities: An array of [start, end] arrays. start and end are non-negative integers representing time, where start < end for all activities.
  • Returns: A single integer, representing the maximum number of non-overlapping activities that can be scheduled.

Clarifications

  • Non-overlapping definition: Two 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.
  • Empty input: If the activities array is empty, the function should return 0.
  • Time values: All time values (start, end) are integers.

Examples

1

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]].

  1. Select [2, 3]. Current lastEnd = 3. Count = 1.
  2. [1, 5] starts at 1, which is less than lastEnd (3). Overlaps. Skip.
  3. [4, 6] starts at 4, which is greater than or equal to lastEnd (3). Select. Current lastEnd = 6. Count = 2.
  4. [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.
2

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].

3

Example 3

Input:

activities = [[1, 3], [2, 4], [3, 5]]

Output:

2

Note:

Sorted by end time: [[1, 3], [2, 4], [3, 5]].

  1. Select [1, 3]. Current lastEnd = 3. Count = 1.
  2. [2, 4] starts at 2, which is less than lastEnd (3). Overlaps. Skip.
  3. [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

Constraints & assumptions

  • 0 <= activities.length <= 10^5
  • 0 <= start < end <= 10^9 for each activity [start, end].
  • The input array activities is not guaranteed to be sorted.

What interviewers evaluate

  • Correctness of Greedy Strategy: The solution correctly applies the greedy principle to find the optimal number of non-overlapping activities.
  • Efficiency: The implementation demonstrates optimal time complexity, typically O(N log N) due to sorting, where N is the number of activities.
  • Edge Case Handling: The code correctly addresses scenarios such as an empty input array or activities that exactly touch at their start/end times.
  • Code Clarity: The solution is well-structured, readable, and easy to understand.

Loading editor...