Maximize Non-Overlapping Customer Interactions
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.
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:
intervals: An array of arrays of numbers, where each inner array [start, end] represents an interaction window. start and end are integers.Output:
intervals array is empty or null, return 0.[start, end], it is guaranteed that start <= end.[a, b] and [c, d] do not overlap if b <= c or d <= a. They overlap if a < d and c < b.Examples
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.
Example 2
Input:
intervals = [[1,2],[1,2],[1,2]]
Output:
1
Note:
All intervals overlap. We can only pick one at most.
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.
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
0 <= intervals.length <= 10^5intervals[i].length == 2-10^9 <= start_i <= end_i <= 10^9intervals may not be sorted.[end, start] where end < start).O(N log N) for time due to sorting.Loading editor...