Frontend School

Optimal Trade Scheduling

DSA
easy

Optimal Trade Scheduling

Easy
Greedy
Arrays
Sorting

Overview

Zerodha, as a leading stockbroker, processes millions of trade orders daily. Optimizing the execution of these orders is paramount for maintaining system efficiency and client satisfaction. Imagine a scenario where you're given a list of potential trade intervals, each defined by a start and an end time. Your task is to select the maximum number of trades that can be executed without any time overlap, ensuring our trading systems are utilized as effectively as possible.

What you need to do / Task

Implement a function maxNonOverlappingTrades that determines the maximum number of trades that can be scheduled from a given list of trade intervals such that no two selected trades overlap.

Input & output

Input:

  • trades: An array of arrays, where each inner array [start_i, end_i] represents a trade interval. start_i is the beginning time of the trade, and end_i is the completion time.

Output:

  • A single number representing the maximum count of non-overlapping trades that can be scheduled.

Clarifications

  • Overlap Definition: Two trades [a, b] and [c, d] are considered overlapping if max(a, c) < min(b, d). If one trade ends exactly when another begins (e.g., [1, 5] and [5, 10]), they are not considered overlapping and can both be scheduled.
  • Empty Input: If the trades array is empty, the function should return 0.
  • Order: The input trades array is not necessarily sorted.

Examples

1

Example 1

Input:

trades = [[1,3],[2,4],[3,5]]

Output:

2

Note:

Trades are: [1,3], [2,4], [3,5]. Sorted by end time: [1,3], [2,4], [3,5].

  1. Pick [1,3]. lastEndTime = 3. count = 1.
  2. [2,4] starts at 2, which is < 3. Overlaps. Skip.
  3. [3,5] starts at 3, which is >= 3. Pick [3,5]. lastEndTime = 5. count = 2. Maximum non-overlapping trades: [1,3] and [3,5].
2

Example 2

Input:

trades = [[10,20],[1,5],[6,12],[15,25]]

Output:

3

Note:

Trades are: [10,20], [1,5], [6,12], [15,25]. Sorted by end time: [1,5], [6,12], [10,20], [15,25].

  1. Pick [1,5]. lastEndTime = 5. count = 1.
  2. [6,12] starts at 6, which is >= 5. Pick [6,12]. lastEndTime = 12. count = 2.
  3. [10,20] starts at 10, which is < 12. Overlaps. Skip.
  4. [15,25] starts at 15, which is >= 12. Pick [15,25]. lastEndTime = 25. count = 3. Maximum non-overlapping trades: [1,5], [6,12], [15,25].
3

Example 3

Input:

trades = [[1,2],[1,2],[1,2]]

Output:

1

Note:

All trades overlap. Only one trade can be selected, e.g., [1,2].

Constraints

Constraints & assumptions

  • 0 <= trades.length <= 10^4
  • trades[i].length == 2
  • 0 <= start_i < end_i <= 10^9
  • All start_i and end_i values are integers.

What interviewers evaluate

  • Correctness: Does the solution accurately identify the maximum number of non-overlapping trades?
  • Efficiency: Is the chosen algorithm efficient enough for the given constraints (e.g., O(N log N) time complexity)?
  • Edge Cases: Does the solution handle cases like empty input or a single trade correctly?
  • Clarity & Readability: Is the code well-structured, easy to understand, and maintainable?

Loading editor...