Pattern : 2 DSA + 1 SQL

An operating system has n tasks numbered from 1 to n.

You are given:

• high_priority: 1-based indices of high-priority tasks.
• t_normal: processing time for a normal task.
• t_high: processing time for a high-priority task.

The tasks must be divided into exactly two contiguous parts:

Prefix: tasks 1 ... k
Suffix: tasks k+1 ... n

where 0 <= k <= n.

• Core 1 processes the prefix.
• Core 2 processes the suffix.
• Both cores work in parallel.

Therefore, the total processing time for a split is:

max(prefix_time, suffix_time)

Find the minimum possible total processing time.

Constraints

1 <= n <= 10^5
0 <= high_priority.length <= n
1 <= high_priority[i] <= n
1 <= t_normal < t_high <= 1000
high_priority contains unique values

Example

Input:

n = 5
high_priority = [2, 4]
t_normal = 2
t_high = 5

The task processing times are:

[2, 5, 2, 5, 2]

Split Evaluation

k = 0 → max(0, 16)   = 16
k = 1 → max(2, 14)   = 14
k = 2 → max(7, 9)    = 9
k = 3 → max(9, 7)    = 9
k = 4 → max(14, 2)   = 14
k = 5 → max(16, 0)   = 16

The minimum processing time is:

9

It is achieved by splitting at:

k = 2
k = 3

Expected result:

9