UptoSkills Arena Batch Job Sorter
The UptoSkills Arena servers run batch jobs. Each job has a submission time (s) and a processing time (p). Jobs are processed strictly in the order they are submitted. However, the system can preempt a job, meaning it can stop a running job and start a new one. If a job is preempted, it resumes later from where it left off.
To optimize resource usage, the administrator wants to process jobs in a specific order: if two jobs have the same submission time, the one with the shorter processing time should be considered first. If submission times are different, the earlier submission time is prioritized. Your task is to determine the order in which jobs are started for the first time.
Input
The first line contains an integer N, the number of jobs. The next N lines each contain two integers S_i and P_i, the submission time and processing time for job i.
Output
Print N integers, the 1-based indices of the jobs in the order they are first started.
Constraints
1 <= N <= 200000 1 <= S_i, P_i <= 10^9
Example 1
3 10 5 10 3 5 8
3 2 1
Job 3 (5, 8) comes first. Then Job 2 (10, 3) before Job 1 (10, 5) due to shorter processing time.
Example 2
4 1 10 2 5 1 12 2 3
1 3 4 2
Jobs submitted at time 1 are Job 1 (1, 10) and Job 3 (1, 12). Job 1 starts first. Jobs submitted at time 2 are Job 2 (2, 5) and Job 4 (2, 3). Job 4 starts before Job 2.
Hints
Similar problems
- Minimum Operations to Make Array SortedMedium
- Minimum Absolute DifferenceEasy
- Maximum Non-overlapping IntervalsMedium
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
- Minimize Maximum DifferenceMedium
More topics: Arrays problems, Sorting problems, Greedy problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 10 5 10 3 5 8
4 1 10 2 5 1 12 2 3