cswork / libraryOpen practice workspace

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

  1. Choose a representation that makes the core operation simple.
  2. Handle empty and boundary inputs before the main algorithm.