PROBLEM LINK:
Author: Akash Rakshit
Editorialist: Akash Rakshit
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
Segment Tree, Map
PROBLEM:
There are N groups in total. You are given the in time, I and out time, O of all the groups with their group size S. In a certain time range l to r, find the maximum numbers of students.
EXPLANATION:
This problem can be solved using segment tree, but the main problem is the constraints. But observe carefully that total number of integers including intime, outtime, size, l and r is not more than 10^6. So we can assign each integers a new number and work on those assigned numbers. We can use set our map to collect all the distinct numbers and assign the new number to those integers. For details, you can see the code.
Here in this problem we ccan see that all the updates are at one place and all the queries are after the updation process. So, in this case we can use this trick to calculate the updation step.
We get the array having total number of students at each time. Now we can simply use segment tree to find the range maximum.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.