Process endpoints in order to find peak concurrency and handle starts and finishes that share a timestamp.
Sweep line algorithm
A sweep line algorithm moves through space or time in order, updating its state only at events that can change it. In computational geometry, a line might sweep across segment endpoints and intersections. On a time axis, the same idea can find the peak number of simultaneous backtest jobs by visiting only their start and finish times. MIT 6.854 lecture notes on sweep algorithms
Follow the endpoints
A job with interval [s,e) is active when s≤t<e. A worker is occupied at the start and available again at the finish. Assume each job needs one worker for its entire run and a freed worker can be reused immediately.
Write two events for each job, +1 at the start and −1 at the finish. Sort the events by time and add up the changes at each distinct timestamp before recording the new active count. The count is a prefix sum of the grouped changes. At each timestamp it includes every job that has started, with every job that has already finished subtracted. Between endpoints, no job can start or finish, so the largest recorded count is the peak. Antti Laaksonen, Competitive Programmer’s Handbook, Chapter 30
The handoff at minute 4
Three fictional backtest jobs run over [1,4), [3,6) and [4,7) minutes. After processing events at minutes 1, 3, 4, 6 and 7, the respective counts are 1, 2, 2, 1 and 0. Two workers are enough. Job A and job B occupy both workers before minute 4, then job C takes the worker released by A.
Three illustrative jobs run from minutes 1 to 4, 3 to 6 and 4 to 7, with starts included and finishes excluded. At minute 4, A ends and C begins while B continues. The active count stays at its peak of 2.
The job on one worker changes at minute 4. The total number of occupied workers stays flat.
At minute 4 the net change is zero. If you process events one by one, process finishes before starts for these nonempty half-open intervals. Counting the start first gives a temporary count of 3 before the finish brings it back to 2. No instant has all three jobs active under the declared convention. With closed intervals, both jobs include the shared endpoint, so the count at that point includes both.
Sorting cost and timing rules
For n jobs, comparison-sorting the 2n events takes O(nlogn) time. The pass over those sorted events takes O(n) time. The event list uses O(n) space, and a count-only scan uses constant extra space once the events are in order. If the endpoint stream already comes in timestamp order, the scan is linear without a sort. These costs are for peak interval overlap. A geometric sweep that reports intersections may also need to maintain which segments cross the line and discover new events during the scan. MIT 6.854 notes on segment intersections
In research, the same count measures label concurrency when several training labels use the same return increments. Define membership using the increments that enter each outcome. For a historical model fit, include only labels whose outcomes were usable by the fit time. A label's start time can precede the cutoff even though its realised exit is still in the future. The SelfMadeQuant Labels and Overlapping Outcomes lesson works through shared increments and training eligibility. The preview is public and the full lesson requires membership.
