FastPrep
Problem · Greedy

Optimize Context Switching

● HardLinkedInOA

A team must optimize context switching between processes. There are n segments where a thread is assigned to each segment. The maximum stack size of a thread assigned in the ith segment is denoted by threadSize[i], for all 1 ≤ i ≤ n. For any high-priority process, some stack size of the segments must be increased. A segment is said to be special when threadSize[i - 1] < threadSize[i] > threadSize[i + 1]. The segments at each end cannot be special. The stack sizes must be modified in such a way as to maximize the number of special segments. To do so, choose any segment and increase the stack size by x. More formally,

  1. Choose an index i and an integer x, where 0 ≤ x ≤ 10^18.
  2. Increase the stack size of the ith segment from threadSize[i] to threadSize[i] + x.

Find the minimum total increase in the stack size of the segments.

Examples
01 · Example 1
threadSize = [3, 1, 4, 5, 5, 2]
return = 3
Example 1 illustration

It is optimal to add 2 and 1 to the third and fifth segments, respectively. The final stack sizes of the segments are [3,1,6,5,6,2].

So the answer = 2 + 1 = 3.

It can be seen that with this change, the required configuration is achieved with a maximum possible of 2 special segments. This is the minimum possible total increase in the stack sizes.

02 · Example 2
threadSize = [3, 2, 1, 2, 3]
return = 4

Since, the segments at the end cannot be special, both the 2nd and 4th segments must be increased by 2. The final stack sizes are [3, 4, 1, 4, 3].

Constraints
🍉🍉
More LinkedIn problems
drafts saved locally
public long optimizeContextSwitching(int[] threadSize) {
  // write your code here
}
threadSize[3, 1, 4, 5, 5, 2]
expected3
sign in to submit