Coding questions · Morgan Stanley
Compute maximum non-overlapping meetings
This question evaluates understanding of interval scheduling and related algorithmic concepts, including complexity analysis, handling of boundary conditions, and management of large input sizes.
Assume you are given a list of meeting time intervals for a single person.
Each meeting i is represented by a pair of integers [start_i, end_i], where 0 <= start_i < end_i, and all times are in the same unit.
You can attend at most one meeting at any given time, and you must attend a meeting for its entire duration if you choose it. Meetings that touch at a boundary (for example, one ends at time t and another starts at time t) do not overlap and can both be attended.
Write a function that, given the list of intervals, returns the maximum number of meetings you can attend by selecting a subset of non-overlapping intervals.
You may assume:
- 1 <= n <= 2 * 10^5
- |start_i|, |end_i| <= 10^9
Clarify the algorithmic problem and return the maximum count of meetings; implementation details are not required here.
Maximum Non-Overlapping Meetings
Return the maximum number of full meetings that can be attended when boundary-touching meetings are allowed.
Examples
Example 1
Input: ([[0,30],[5,10],[10,20]],)
Output: 2
Explanation: Choose two short meetings.
Example 2
Input: ([[1,2],[2,3],[3,4]],)
Output: 3
Explanation: Touching boundaries allowed.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.