1. Process Scheduler
Process scheduling algorithms are used by a CPU to optimally schedule the running processes. A core can execute one process at a time, but a CPU may have multiple cores.
There are n processes where the iᵗʰ process starts its execution at start[i] and ends at end[i], both inclusive. Find the minimum number of cores required to execute the processes.
Example
n = 3
start = [1, 3, 4]
end = [3, 5, 6]
If the CPU has only one core, the first process starts at 1 and ends at 3. The second process starts at 3. Since both processes need a processor at 3, they overlap. There must be more than 1 core.
If the CPU has two cores, the first process runs on the first core from 1 to 3, the second runs on the second core from 3 to 5, and the third process runs on the first core from 4 to 6.
Return 2, the minimum number of cores required.
Function Description
Complete the function getMinCores in the editor below.
getMinCores takes the following arguments:
- int start[n]: the start times of processes
- int end[n]: the end times of processes
Returns
int: the minimum number of cores required
Constraints
1 ≤ n ≤ 10⁵
1 ≤ start[i], end[i] ≤ 10⁹
Sample Input For Custom Testing
STDIN
3
1 2 3
3 3 5
Function
start[] size n = 3
start = [1, 2, 3]
end[] size n = 3
end = [3, 3, 5]
Sample Output
3
Explanation
Using 2 cores, the first and second processes finish at time 3. The third process starts at 3. Given the conflict, there must be at least 1 more core.
2. Transaction Simplification
Implement a prototype service to simplify a group of debt transactions.
There are n people, and a list of m debts amongst them where debts[i] = [from[i], to[i], amount[i]] represents that person from[i] owes the person to[i] an amount of amount[i].
Given the array debts, find the minimum number of transactions required to clear all the debts.
Example
Suppose n = 3, m = 4, debts[] = [[0, 1, 20], [1, 0, 5], [1, 2, 10], [2, 0, 10]]
Suppose 0 gives 1 a total amount of 5 units.
| from | to | amount |
|---|---|---|
| 0 | 1 | 20 - 5 = 15 |
| 1 | 0 | 5 |
| 1 | 2 | 10 |
| 2 | 0 | 10 |
Also, 1 owed 0 5 units, so reduce the debt from 1 to 0 by that 5 units. Now 0 and 1's debts are simplified.
| from | to | amount |
|---|---|---|
| 0 | 1 | 10 |
| 2 | 0 | 10 |
The three transactions can now cancel each other out. Only one transaction is required to clear all the debts, i.e., from 0 to 1. Hence, the answer is 1.
Function Description
Complete the function getMinTransactions in the editor below.
getMinTransactions has the following parameters:
- n: the number of people
- debt[m][3]: the debts
Returns
int: the minimum number of transactions required
Constraints
2 ≤ n ≤ 9
2 ≤ m ≤ 10⁵
0 ≤ debt[i][0], debt[i][1] < n
1 ≤ debt[i][2] ≤ 10⁹
Sample Input For Custom Testing
Sample Case 0
STDIN
3
2
3
0 1 10
2 0 5
Function
n = 3
m = 2
size of debt[i] = 3
debts[] = [[0, 1, 10], [2, 0, 5]]
Sample Output
2
Explanation
Person 2 must pay person 0 5 units, and person 0 must pay person 1 10 units.
Sample Case 1
STDIN
4
4
3
1 2 15
3 2 14
0 3 10
3 1 20
Function
n = 4
m = 4
size of debt[i] = 3
debts[] = [[1, 2, 15], [3, 2, 14], [0, 3, 10], [3, 1, 20]]
Sample Output
3
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
