Frontend School

Maximize Non-Overlapping Customer Interactions

DSA
medium

Maximize Non-Overlapping Customer Interactions

Medium
Intervals
Greedy
Sorting

Overview

Intuit provides various financial services, and optimizing customer support is crucial. Imagine you have a list of scheduled customer interaction windows (e.g., support calls, online chat sessions) for a particular agent or team. Each window is defined by a start and end time. To ensure optimal service and avoid conflicts, an agent can only handle one interaction at a time. Your task is to determine the maximum number of customer interactions an agent can successfully complete without any overlaps.

What you need to do / Task

Given an array of intervals, where each interval[i] = [start_i, end_i] represents a customer interaction window, find the maximum number of non-overlapping intervals you can select. An interval [a, b] and [c, d] are considered overlapping if max(a, c) < min(b, d). This means [1,2] and [2,3] are not overlapping, as one ends exactly when the other begins, allowing for sequential handling. However, [1,3] and [2,4] are overlapping.

Input & output

Input:

  • intervals: An array of arrays of numbers, where each inner array [start, end] represents an interaction window. start and end are integers.

Output:

  • A single integer representing the maximum number of non-overlapping intervals that can be selected.

Clarifications

  • Empty Input: If the intervals array is empty or null, return 0.
  • Interval Definition: For an interval [start, end], it is guaranteed that start <= end.
  • Overlapping Definition: Two intervals [a, b] and [c, d] do not overlap if b <= c or d <= a. They overlap if a < d and c < b.

Examples

1

Example 1

Input:

intervals = [[1,2],[2,3],[3,4],[1,3]]

Output:

3

Note:

The intervals [[1,2], [2,3], [3,4]] are non-overlapping. Although [1,3] overlaps with [1,2] and [2,3], we can still pick 3 non-overlapping intervals.

2

Example 2

Input:

intervals = [[1,2],[1,2],[1,2]]

Output:

1

Note:

All intervals overlap. We can only pick one at most.

3

Example 3

Input:

intervals = [[1,2],[2,3]]

Output:

2

Note:

These intervals do not overlap. An interaction ending at 2 can be immediately followed by one starting at 2.

4

Example 4

Input:

intervals = [[1,10],[2,3],[4,5],[6,7]]

Output:

3

Note:

We can pick [[2,3],[4,5],[6,7]]. Picking [1,10] would prevent picking any of the others. The maximum is 3.

Constraints

Constraints & assumptions

  • 0 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -10^9 <= start_i <= end_i <= 10^9
  • The input array intervals may not be sorted.

Out of scope

  • Handling invalid interval formats (e.g., [end, start] where end < start).
  • Optimizing for multiple agents or complex scheduling rules.

What interviewers evaluate

  • Correctness: The solution must accurately identify the maximum number of non-overlapping intervals for all valid inputs.
  • Efficiency: The solution should have an optimal time and space complexity, typically O(N log N) for time due to sorting.
  • Edge Cases: The solution should correctly handle edge cases such as empty input, single interval, all overlapping intervals, or no overlapping intervals.
  • Clarity & Readability: The code should be well-structured, easy to understand, and follow good programming practices.

Loading editor...