August Long Challenge Charge Scheduling Solution

Charge Scheduling Solution

There are NN people in a train and each of them gets on the train at time t=0t=0.

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.

The ithith person wants to use the charging station for AiAi minutes in total and will leave the train at time TiTi. A person will be satisfied after the journey, only if that person gets to use the charging station for the desired amount of time.

Also See: August Long Challenge 2021 Solutions

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 [L,R)[L,R), and ask the person ii to use the charging station from t=Lt=L and leave just before t=Rt=R. After this the person ii would have spent R−LR−L minutes on the charging station and any person who is still on the train can begin using the charging station starting from t=Rt=R. 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 [L,R)[L,R) and [R,S)[R,S) do not intersect each other.
• For all people ii and all intervals [L,R)[L,R) assigned to ii, 0≤L≤R≤Ti0≤L≤R≤Ti, 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 than 2N2N intervals. 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.

Input Format

• The first line contains a single integer QQ denoting the number of test cases. The description of QQ test cases follows.
• Each test case contains 33 lines of input.
• The first line of each test case contains a single integer NN, the number of people on the train.
• The second line of each test case contains NN space-separated integers, A1,A2,…ANA1,A2,…AN, where AiAi is the amount of time that the ithith person needs to use the charger.
• The third line of each test case contains NN space separated integers, T1,T2,…TnT1,T2,…Tn, where TiTi is the time at which the ithith person leaves the train.

Output Format

• For each test case, in the first line, print a single integer M(≤2N)M(≤2N), the number of different intervals that you want to schedule.
• MM lines follow. For each valid ii, the ithith of these lines should contain three space-separated integers, i,L,Ri,L,R denoting that the person ii should use the charging station from [L,R)[L,R).
• 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.

Constraints

• 1≤Q≤3⋅1051≤Q≤3⋅105
• 1≤N≤3⋅1051≤N≤3⋅105
• 0≤Ai≤3⋅1050≤Ai≤3⋅105 for each valid ii
• 0≤Ti≤3⋅1050≤Ti≤3⋅105 for each valid ii
• The sum of NN over all testcases does not exceed 3⋅1053⋅105

Subtasks

• Subtask #1 (10 points) : TiTi-s are equal for all NN 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

Explanation

Test case 1: Person 11 and Person 44 can never be satisfied because the time they spend on the train (1414 and 44 respectively) is less than the amount of time they want to spend for charging. The other three people can be assigned as shown (Person 33 in the interval [0,6)[0,6), Person 55 in the interval [6,13)[6,13) and finally Person 22 in the interval [13,45)[13,45). Note that there are multiple solutions, for example, we could have also assigned Person 55 to [0,7)[0,7) and Person 33 to [7,13)[7,13) instead. Both are considered correct.

Test case 2: Person 11 and Person 22 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 30+11+22=6330+11+22=63, but t=49t=49, all of them would have left the train. However we can select either Persons 33 and Person 44 or Person 44 and Person 55 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 00.

Test case 4: Apart from Person 22 (who has a very low charging time), we cannot hope to satisfy more than 22 of the others. This is because the sum of the 33 least times is already 5858 and everyone would have left the train by t=50t=50. Therefore the maximum number of people we can hope to satisfy is 33, and the given solution constructs it.

Solution:

Program C++:

#include<bits/stdc++.h>
using namespace std;

bool compare(vector<int> &a,vector<int> &b){
    
    if(a[0]==b[0]) return a[1]<b[1];
    
    return a[0]<b[0];
}

int main()
{
    
  int testcase;
  cin >> testcase;
  
  while(testcase--) {
        
        int n;
        cin>>n;
        vector<int> tmp;
        vector<int> tmp2;
        vector<vector<int>> v;
        int timeNeed,y;
        for(int i=0;i<n;i++){
            cin>>timeNeed;
            tmp.push_back(timeNeed);
        }
        
        for(int i=0;i<n;i++){
            cin>>y;
            tmp2.push_back(y);
            if(tmp[i]<=y)
                 v.push_back({y,tmp[i],i});
         }
       
       /*for(auto ele:v){
           cout<<"["<<ele.first<<" "<<ele.second<<"] ";
       }*/
       
       sort(v.begin(),v.end(),compare);
       
       int last_time=0;
       
       int len=v.size(),count=0;
       
       
       vector<vector<int>> ans;
       
       //dfs(v,count,ans);
       
       priority_queue<pair<int,int>> pq;
       
       for(int i=0;i<len;i++){
           
           int chargetime=v[i][1];
           int index=v[i][2];
           int exittime=v[i][0];
           if(last_time+chargetime<=exittime){
               pq.push({chargetime,index});
               last_time+=chargetime;
           }
           else{
               
               pair<int,int> p=pq.top();
               int oldchargetime=p.first;
               
               if(oldchargetime>chargetime){
                   pq.pop();
                   pq.push({chargetime,index});
                   
                   last_time=last_time-oldchargetime+chargetime;
               }
           }
           
       }
       
       last_time=0;
       
       while(!pq.empty()){
           
           pair<int,int> p=pq.top();
           pq.pop();
           int index=p.second;
           
           ans.push_back({tmp2[index],tmp[index],index});
           
       }
       
     
      sort(ans.begin(),ans.end(),compare);
       
      cout<<ans.size()<<endl;
      
      for(auto ele:ans){
          cout<<ele[2]+1<<" "<<last_time<<" "<<last_time+ele[1]<<endl;
          
          last_time+=ele[1];
      } 
      
    
        
    }
    
    
    return 0;
}  

import heapq


for t in range(int(input())):
    n = int(input())
    *a, = map(int, input().split())
    *t, = map(int, input().split())
    people = sorted(filter(lambda i: i[0] >= i[1], zip(t, a, range(1, n+1))))
    heap = []
    current = 0
    for i in people:
        deadline = i[0]
        time = i[1]
        # print(i, heap)
        if current + time <= deadline:
            heapq.heappush(heap, [-time, i[2]])
            # current += time
        else:
            assert len(heap) != 0
            largest = -heap[0][0]
            if time >= largest:
                continue
            elif current + time - largest <= deadline:
                heapq.heappushpop(heap, [-time, i[2]])
            current -= largest
        current += time
    print(len(heap))
    people_to_take = sorted([[t[i[1]-1], a[i[1]-1], i[1]] for i in heap])
    current_time = 0
    for i in people_to_take:
        print(i[2], current_time, current_time+i[1])
        current_time += i[1]