University career fair has a list of companies along with their respective arrival times and the duration of their stay.

Only one company can present at a time.

Given each company's arrival time and duration they will stay, determine the maximum number of presentations that can be hosted during career fair.

Solution

First sort the event according to (end_time(start_time+duration), start_time) in ascending order.

Then Initialize a variable as previous_end_time = 1 and ans =0.

If for the current event the start_time is greater or equal to previous_end_time, increment ans, update previous_end_time as the end time for current event otherwise ignore the current event

code

ll n;
cin >> n;
vector<ll> a(n), b(n);
for (ll i = 0; i < n; i++)
{
cin >> a[i];
}
for (ll i = 0; i < n; i++)
{
cin >> b[i];
}
vector<pll> vp;
for (ll i = 0; i < n; i++)
{
vp.pb({a[i] + b[i], a[i]}); // pushing pairs as {r,l}
}
sort(all(vp)); // sort the vector in increasing order of r values
ll ans = 0; // initialse answer as 0
ll pr = 1; // initialse previous r value as 1
for (ll i = 0; i < n; i++)
{
if (vp[i].ss >= pr)// if the l value is greater than or equal to previous r value
{
ans++;
pr = vp[i].ff;// set the new pr value as current r value
}
}
cout << ans << endl;
return;