Charge Scheduling solution codechef
There arepeople in a train and each of them gets on the train at time .
Each person on the train wants to use the charging station on the train for some amount of time, but unfortunately, the train has only one charging station and can only be used by 1 person at any point in time.
Theperson wants to use the charging station for minutes in total and will leave the train at time . A person will be satisfied after the journey, only if that person gets to use the charging station for the desired amount of time.
Find a way to schedule the charging such that a maximum number of people is satisfied. In order to schedule, you can pick any interval of time, say, and ask the person to use the charging station from and leave just before . After this the person would have spent minutes on the charging station and any person who is still on the train can begin using the charging station starting from . An interval scheduling will be a set of time intervals and people assigned to those intervals.
A schedule is valid if:
- No two intervals in the schedule intersect each other. Note that all and do not intersect each other.
- For all people and all intervals assigned to , , i.e. each person is not assigned to an interval of time when they are not on the train.
You have to find optimal scheduling that does not contain more thanintervals. It is guaranteed that there always exists optimal scheduling with the given constraints. If there are many such schedules, you can output any of them.
- The first line contains a single integer denoting the number of test cases. The description of test cases follows.
- Each test case contains lines of input.
- The first line of each test case contains a single integer , the number of people on the train.
- The second line of each test case contains space-separated integers, , where is the amount of time that the person needs to use the charger.
- The third line of each test case contains space separated integers, , where is the time at which the person leaves the train.
- For each test case, in the first line, print a single integer , the number of different intervals that you want to schedule.
- lines follow. For each valid , the of these lines should contain three space-separated integers, denoting that the person should use the charging station from .
- The number of satisfied people should be maximum.
- The scheduling should be valid.
- It is possible to schedule the same person multiple times.
- The order in which the intervals are displayed does not matter.
- for each valid
- for each valid
- The sum of over all testcases does not exceed
- Subtask #1 (10 points) : -s are equal for all people
- Subtask #2 (90 points) : Original constraints
Sample Input 1
4 5 31 32 6 13 7 14 50 34 4 31 5 43 26 22 11 30 26 4 41 46 49 5 36 40 49 19 37 18 11 48 15 33 5 16 3 24 21 21 24 31 36 49 50
Sample Output 1
3 3 0 6 5 6 13 2 13 45 2 4 0 11 3 11 33 0 3 2 0 3 1 3 19 4 19 40
Test case 1: Personand Person can never be satisfied because the time they spend on the train ( and respectively) is less than the amount of time they want to spend for charging. The other three people can be assigned as shown (Person in the interval , Person in the interval and finally Person in the interval . Note that there are multiple solutions, for example, we could have also assigned Person to and Person to instead. Both are considered correct.
Test case 2: Personand Person can never be satisfied (they spend less time on the train than the amount of time they need to use the charging station). Among the remaining three, we cannot satisfy all of them, since the total time required would be , but , all of them would have left the train. However we can select either Persons and Person or Person and Person and schedule them in any order, and in both cases, both of the persons would be satisfied.
Test case 3: No one can be satisfied and hence the answer is.
Test case 4: Apart from Person(who has a very low charging time), we cannot hope to satisfy more than of the others. This is because the sum of the least times is already and everyone would have left the train by . Therefore the maximum number of people we can hope to satisfy is , and the given solution constructs it.