Optimal Trade Scheduling
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.
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:
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:
number representing the maximum count of non-overlapping trades that can be scheduled.[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.trades array is empty, the function should return 0.trades array is not necessarily sorted.Examples
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].
lastEndTime = 3. count = 1.lastEndTime = 5. count = 2.
Maximum non-overlapping trades: [1,3] and [3,5].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].
lastEndTime = 5. count = 1.lastEndTime = 12. count = 2.lastEndTime = 25. count = 3.
Maximum non-overlapping trades: [1,5], [6,12], [15,25].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
0 <= trades.length <= 10^4trades[i].length == 20 <= start_i < end_i <= 10^9start_i and end_i values are integers.Loading editor...