← 返回 ibm 的题目列表Process Execution Time (Merge Inclusive Intervals)
类型:qbank
Given arrays of process start and end times, compute the total amount of time during which at least one process is running. Endpoints are inclusive, so merged interval length is `end - start + 1`.
Requirements
Function: getExecutionTime(start, end).
Input: int start[n] and int end[n], where start[i] <= end[i].
Output: an integer denoting total time during which at least one process was running.
Intervals are inclusive at both ends.
Constraints include n up to 2 * 10^5 and times up to 10^9, so an interval merge or sweep-line solution is expected.
Examples
n = 3
start = [1, 2, 8]
end = [5, 6, 10]
Output: 9
[1,5] and [2,6] merge to [1,6], contributing 6; [8,10] contributes 3.
Notes
Sort intervals by start time, maintain the current merged range, and add cur_end - cur_start + 1 when a component closes.
Use 64-bit arithmetic if the implementation language's integer range is narrow; the sum of interval lengths can exceed a small signed integer.
A separate IBM OA only named a direct merge-intervals question, which matches this family but did not include full input/output detail.
Preparation
Write the merge loop from memory with an inclusive length formula, then rerun it on touching intervals such as [1,4] and [4,5].
Practise explaining why sorting by start is enough, why the accumulator should be 64-bit in Java/C++ style languages, and why coordinate expansion is unacceptable for large timestamps.