Space Station Shuttle — Minimum Total Tourist Travel Time

Problem Statement

Space Station Shuttle — Minimum Total Tourist Travel Time A tourist agency runs a single shuttle along a line of N space stations numbered 1 to N . The shuttle starts at station 1 and moves sequentially: station 1 to station 2 , then station 2 to station 3 , and so on up to station N . Travelling from station i to station i + 1 takes D[i] minutes. You own K nitrogen accelerators. Each accelerator can be installed on one segment and permanently reduces that segment's travel time by 1 minute. Several accelerators may be installed on the same segment, and a segment's travel time can never drop below 0 minutes. You do not have to install all of them. There are M tourists. Tourist i reaches station A[i] at minute T[i] and wants to get off at station B[i] , where A[i] < B[i] . Before leaving a station, the shuttle waits there until every tourist who boards at that station has arrived. The shuttle begins its run at station 1 at minute 0 (inferred — the source states only that the shuttle m