Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- class triplet{
- public:
- int si, ei;
- long long pi;
- triplet(int si, int ei, long long pi){
- this-> si = si;
- this-> ei = ei;
- this-> pi = pi;
- }
- };
- bool compare(const triplet &t1, const triplet &t2){
- if(t1.si == t2.si){
- return t1.ei <= t2.ei ? true : false;
- }
- return t1.si < t2.si ? true : false;
- }
- void getMaxProfitByAttendingMeetings(int level, int si, int ei, long long currProfit, long long &maxProfit, vector<triplet> &projects){
- if(level >= projects.size()){
- maxProfit = max(maxProfit, currProfit);
- return;
- }
- //attend
- if(projects[level].ei < si || projects[level].si > ei){
- getMaxProfitByAttendingMeetings(level + 1, min(projects[level].si, si), max(projects[level].ei, ei), currProfit + projects[level].pi, maxProfit, projects);
- }
- //don't attend
- getMaxProfitByAttendingMeetings(level + 1, si, ei, currProfit, maxProfit, projects);
- }
- int findNextMeetingThatCanBeAttendedIfIthMeetingAttended(int endTime, int level, vector<triplet> &projects){
- int l = level + 1, r = projects.size() - 1, idx = -1;
- while(l <= r){
- int mid = (r - l) / 2 + l;
- if(projects[mid].si > endTime){
- idx = mid;
- r = mid - 1;
- }
- else{
- l = mid + 1;
- }
- }
- return idx;
- }
- long long getMaxProfitByAttendingMeetingsMemo(int level, vector<triplet> &projects, vector<long long> &memo){
- if(level >= projects.size()){
- return 0;
- }
- if(memo[level] != -1){
- return memo[level];
- }
- long long attendedProfit = 0, notAttendedProfit = 0;
- /*
- If we are going to attend ith meeting, or the meeting at current level, what is the JUST next meeting that can be attended. Also we can say WHAT LEVEL we GO next if we choose to attend meeting at current level
- Generally we jump level + 1 in every case (we take decision of at current level, and the move to next level to take decision of that)
- Here we are also doing the same thing.
- If we don't attend the meeting at index 'level' we are not changing the the si or ei, and we can surely attend the next meeting at level + 1, because we didn't attend the meeting at index 'level', as the array is sorted based on start times, the meeting at level + 1 has a start time > meeting at level start time.
- If we attend the meeting at index 'level', we are changing the si & ei. We are going to attend this meeting which might BLOCK the meeting at level + 1, level + 2...upto some level + i..
- BLOCK as in if the meeting at index 'level' ends at some duration ei, then all the meetings at next level(upto some level + i) whose start time <= ei are BLOCKED, simply because these meetings will overlap with our ongoing meeting at index 'level'. The meetings that are blocked START at some time during which our current meeting is going on and hence we can't attend those.
- So the problem is we can't do level + 1, level + 2(if we attend the meeting)
- Unlike the case where we don't attend the current meeting(where we simply do level + 1), because the meeting[level + 1] is automatically a valid option.
- But If we explore the option to attend current meeting[level] - SO WHAT IS THE FIRST CLOSEST MEETING WHICH START AFTER OUR CURRENT MEETING ENDS or WHAT IS THE FIRST MEETING THAT STARTS JUST AFTER OUR CURRENT MEETING ENDS, essentially making it the first valid meeting that can be attended if we choose to attend the meeting[level].
- SO WHAT IS THE FIRST/minimum 'i'/'level + i' where we can jump after we explore the option to attend, first meaning the meeting that has the smallest start time that is atleast larger than the end time of current meeting.
- meeting[level].ei < meeting[level + i].si
- [level, level + 1, level + 2, level + 3, level + 4 ....... level + i......] (sorted based on start times)
- We explored an option (attend), which means we move to the next level. Here the question is, which level to move to next? As moving to (level + 1) is not going to cut it everytime, as if in case the meeting attended at level might go on even after the meeting[level + 1] starts...or meeting[level + 2] starts.....making those meetings blocked and impossible to attend to as you can only attend 1 meeting at a time.
- We need to move to some level + i, where meeting[level + i].si > meeting[level].ei, i.e. the meeting[level + i] only starts after the meeting[level] ends.
- As the array is sorted we can use Binary Search to figure out 'i',as we need to find the meeting whose start time is just larger than the end time of meeting[level]. So whatever 'i' is returned, we move to that level, by calling (level + i).
- */
- int nextValidMeetingIdx = findNextMeetingThatCanBeAttendedIfIthMeetingAttended(projects[level].ei, level, projects);
- //attend
- attendedProfit = projects[level].pi + getMaxProfitByAttendingMeetingsMemo(nextValidMeetingIdx, projects, memo);
- //don't attend
- notAttendedProfit = getMaxProfitByAttendingMeetingsMemo(level + 1, projects, memo);
- return memo[level] = max(attendedProfit, notAttendedProfit);
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- vector<triplet> projects;
- int si, ei;
- long long pi;
- for(int i = 0; i < n; i++){
- cin >> si >> ei >> pi;
- triplet t(si, ei, pi);
- projects.emplace_back(t);
- }
- /*
- Recursive Call
- long long maxProfit = 0;
- getMaxProfitByAttendingMeetings(0, 0, 0, 0, maxProfit, projects);
- cout << maxProfit << '\n';
- */
- /*
- Memo Call
- */
- sort(projects.begin(), projects.end(), compare);
- vector<long long> memo(n, -1);
- cout << getMaxProfitByAttendingMeetingsMemo(0, projects, memo) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
