Optimize Content Publishing Schedule
At Adobe, content is king, and our publishing platforms empower creators to reach vast audiences. A key challenge for content managers is to efficiently schedule articles to maximize visibility. Each article has a specific time window during which it's relevant and can be published. Our platform, however, can only publish one article at any given moment.
This problem asks you to help optimize the publishing schedule by determining the maximum number of articles that can be published without any overlaps, given their start and end times.
You are tasked with implementing a function that takes a list of articles, where each article is represented by its start and end publishing times. Your goal is to select a subset of these articles such that no two selected articles overlap, and the total number of selected articles is maximized.
Input:
articles: An array of arrays (or tuples), where each inner array [start, end] represents an article's publishing window. start is the beginning time and end is the completion time. Both start and end are non-negative integers. An article [s1, e1] is considered to overlap with [s2, e2] if s1 < e2 and s2 < e1. If e1 == s2, they do not overlap (one ends exactly when the other begins).
Output: Return a single integer representing the maximum number of non-overlapping articles that can be published.
articles array is empty, no articles can be published. Return 0.start and end times are integers representing discrete time units (e.g., minutes, hours).[start, end] occupies the time slot from start up to, but not including, end. So [1, 5] and [5, 10] do not overlap.articles array is not necessarily sorted. You should handle this.Examples
Example 1
Input:
articles = [[1, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]
Output:
3
Note:
To maximize non-overlapping articles, sort them by their end times: [[1, 4], [3, 5], [0, 6], [5, 7], [5, 9], [8, 9]]. After sorting, a possible valid sequence of non-overlapping articles is [1, 4], then [5, 7] (since 5 >= 4), then [8, 9] (since 8 >= 7). Total 3 articles.
Example 2
Input:
articles = [[1, 2], [2, 3], [3, 4]]
Output:
3
Note:
All articles can be published sequentially as their start times are exactly equal to the previous article's end time, meaning no overlap. The sorted order is already [[1, 2], [2, 3], [3, 4]]. We can select all three.
Example 3
Input:
articles = [[1, 10], [2, 3], [4, 5]]
Output:
2
Note:
Sorted by end times: [[2, 3], [4, 5], [1, 10]]. We can select [2, 3]. The next article that does not overlap is [4, 5] (since 4 >= 3). The article [1, 10] overlaps with [4, 5] (1 < 5) and cannot be selected. Total 2 articles.
Constraints
0 <= articles.length <= 10^50 <= start_i < end_i <= 10^9 for each article [start_i, end_i]start_i and end_i are integers.Loading editor...