Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Charge Scheduling CodeChef Solution – Queslers
Problem: Charge Scheduling CodeChef 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 11 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.
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.
Charge Scheduling CodeChef Solution Using Python
import heapq
t=int(input())
for z in range(t):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=[]
for i in range(n):
c.append([b[i],i])
c.sort()
t=0
d=[]
for i in c:
if(a[i[1]]<=i[0]):
heapq.heappush(d,[a[i[1]]*(-1),i[1]])
t+=a[i[1]]
if(t>i[0]):
k=heapq.heappop(d)
t-=k[0]*(-1)
print(len(d))
#print(d)
m={}
while(d):
k=heapq.heappop(d)
m[k[1]]=k[0]*(-1)
#print(m)
t=0
for i in c:
if(i[1] in m):
print(i[1]+1,t,t+m[i[1]])
t+=m[i[1]]
Charge Scheduling CodeChef Solution Using C++
#include <bits/stdc++.h>
#define LL long long
using namespace std;
auto random_seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(random_seed);
clock_t start = clock();
LL readInt(LL l, LL r, char endd) {
LL x = 0;
char ch = getchar();
bool first = true, neg = false;
while (true) {
if (ch == endd) {
break;
} else if (ch == '-') {
assert(first);
neg = true;
} else if (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
} else {
assert(false);
}
first = false;
ch = getchar();
}
if (neg) x = -x;
if (x < l || x > r) {
cerr << l << " " << r << " " << x << " failed\n";
}
assert(l <= x && x <= r);
return x;
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert (g != -1);
if (g == endd) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
LL readIntSp(LL l, LL r) {
return readInt(l, r, ' ');
}
LL readIntLn(LL l, LL r) {
return readInt(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
const int M = (int)3e5;
const int C = (int)3e5;
int sum_n = 0;
array<int, 3> v[M];
void solve() {
int n = readIntLn(1, M);
sum_n += n;
for (int i=0;i<n;++i) {
v[i][1] = readInt(0, C, " \n"[i==n-1]);
v[i][2] = i;
}
for (int i=0;i<n;++i) v[i][0] = readInt(0, C, " \n"[i==n-1]);
sort(v, v+n);
// for (int i=0;i<n;++i) cerr << v[i][0] << " " << v[i][1] << '\n';
set<pair<int, int>> st;
LL have = 0;
for (int i=0;i<n;++i) {
st.insert({v[i][1], i});
// cerr << v[i][1] << " " << "added\n";
if (have + v[i][1] <= v[i][0]) {
have += v[i][1];
} else {
auto it = st.end();
it--;
have += v[i][1] - it->first;
// cerr << it->first << " " << "removed\n";
st.erase(it);
}
}
vector<pair<int, int>> ret;
LL go = 0;
for (auto &p : st) {
int ind = p.second;
// cerr << go + v[ind][1] << " " << v[ind][0] << " wtf\n";
// if (go + v[ind][1] <= v[ind][0]) {
ret.push_back({v[ind][0], ind});
// go += v[ind][1];
// }
}
sort(ret.begin(), ret.end());
int pre = 0;
vector<array<int, 3>> vout;
for (int i=0;i<(int)ret.size();++i) {
int ind = ret[i].second;
// cout << v[ind][2] + 1 << " " << pre << " " << pre + v[ind][1] << '\n';
vout.push_back({v[ind][2]+1, pre, pre+v[ind][1]});
assert(pre + v[ind][1] <= v[ind][0]);
pre += v[ind][1];
}
cout << vout.size() << '\n';
shuffle(vout.begin(), vout.end(), rng);
for (auto it : vout) cout << it[0] << " " << it[1] << " " << it[2] << '\n';
}
int main() {
// Start solution here use readIntLn, readIntSp and readStringSp and readStringLn
// for reading input
int T = readIntLn(1, M);
while (T--) {
solve();
}
assert(1 <= sum_n && sum_n <= M);
// End solution here
assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}Charge Scheduling CodeChef Solution Review:
In our experience, we suggest you solve this Charge Scheduling CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
Charge Scheduling Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Charge Scheduling CodeChef Solution.
Conclusion:
I hope this Charge Scheduling CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More on Queslers >>
