In comparator function pass both vectors by reference instead of pass by value. All test cases will be passed. And also do optimization as Fraz bhaiya said by inserting values 1 to maximum time in set instead of 1e5.
Dude thanks a lot. Passing by reference to the comparator function passed all test cases , earlier i was getting tle. Was stuck on this for several hours.THANK YOU SO MUCH ❤️❤️❤️❤️❤️❤️
Iterating by event (as it is the upper bound), event that is going to end next should be considered first at any given moment - hence the sorting, use of std::set as need to maintain order. Any time based max-min problem has sorting involved.
"We are inserting number of days in the set. Just change it to the maximum day given in array instead of 10^5." but why it gives tle on inserting 10^5 elements in set ...it is well within 10^8 operations (i.e. nlogn = 10^5*log(10^5) = 1.6*10^6)????
Use this those who are getting TLE, to understand this better first study the SJF algorithm from OS and then try this problem, it will be breeze to solve it...Hope it helps class Solution { public: int maxEvents(vector& events) { // introduce a timeline variable --> which will go from day 0 to day n // this is done, because according to question an event spans through a number of days // and we can attend this event anyday in between, so we will basically attend one event // in one day, hence the timeline variable will tell us which event to attend on the particular // day, also for maximum events we will sort the events based on their starting times // and we will use the timeline variable to push those events into the set/pq which have // arrived till that time, and attend the one having lower end time first and so on... int n = events.size(); sort(begin(events), end(events)); int timeline = 0, index = 0; int count = 0; priority_queue minheap; while(index < n || !minheap.empty()){ // edge case when large gap b/w events or start event if(minheap.empty() && timeline < events[index][0]){ timeline = events[index][0]; } // pick the events that have arrived till this timeline while(index < n && events[index][0]
C++ code: bool static comp (vector & a, vector & b) { if (a[1] < b[1]) return true; // sorting acc to end time else if (a[1] == b[1]) return a[0] < b[0]; // sorting acc to start time if same end time return false; } int maxEvents(vector& events) { sort (events.begin(), events.end(), comp); int count = 0; set days; for (int i = 1; i
slightly better java solution class Solution { public int maxEvents(int[][] events) {
// sort the events array by the end date and if they are equal then by start date Arrays.sort(events, new Comparator() { public int compare(int[] a, int[] b) { if (a[1] > b[1]) { return 1; } else if (a[1] == b[1]) { if (a[0] > b[0]) { return 1; } else { return -1; } } else { return -1; } } });
// initilization of vars int counter = 0; int start = 0; int end = 1;
// find the max time and min time to fill the set int max = 0; int min = Integer.MAX_VALUE; for (int row = 0; row < events.length; row++) { max = max > events[row][end] ? max : events[row][end]; min = min < events[row][start] ? min : events[row][start]; }
// create set and fill it with true values, that signifies the days of the event which have not been visited. If false then it is visited boolean[] set = new boolean[max-min+1]; for (int i = min; i
FOR THOSE GETTING TLE. upper_bound(Set.begin(), Set.end(), x) is a function that doesn't know anything about std::set internal structure. Set iterators are not random-access meaning that upper_bound has to perform O(n) iterator movements in order to access any position in the container. That's why you should never use lower_bound/upper_bound with std::set but you can use Set.lower_bound(x)/Set.upper_bound(x) that perform a search over a binary search tree, that works obviously in log n/ So basically use : days.lower_bound(s) Reference: codeforces.com/blog/entry/22074
I was getting TLE using upper_bound(Set.begin(), Set.end(), x) and was wondering wtf is wrong. Surely got something super important to learn. Thanks mate!
your code when run at leetcode is giving TLE so can you please help me to resolve
We are inserting number of days in the set.
Just change it to the maximum day given in array instead of 10^5.
It would solve the problem.😊
@@mohammadfraz it still gives tle for the last test case
@@sitanshushukla1820 Shouldnt you limit it to number of events? your answer can never exceed number of events
@@sitanshushukla1820 Beacuse u have to use segment tree
@@mohammadfraz The time complexity of your solution is not O(n log n)
In comparator function pass both vectors by reference instead of pass by value. All test cases will be passed. And also do optimization as Fraz bhaiya said by inserting values 1 to maximum time in set instead of 1e5.
Dude thanks a lot. Passing by reference to the comparator function passed all test cases , earlier i was getting tle. Was stuck on this for several hours.THANK YOU SO MUCH
❤️❤️❤️❤️❤️❤️
Iterating by event (as it is the upper bound), event that is going to end next should be considered first at any given moment - hence the sorting, use of std::set as need to maintain order. Any time based max-min problem has sorting involved.
"We are inserting number of days in the set.
Just change it to the maximum day given in array instead of 10^5."
but why it gives tle on inserting 10^5 elements in set ...it is well within 10^8 operations (i.e. nlogn = 10^5*log(10^5) = 1.6*10^6)????
what is the logic behind sorting it by end day ??
Thank you so much !!!
Why sorting based on endTime and not the startTime, didn't understand this even in meeting room problem.
we are willing to choose the events which will get finished first ignoring the starting time.
Try for this case: [[1,2],[1,2],[3,3],[1,5],[1,5]]. It will get ugly if we choose sorting based on startTime.
Use this those who are getting TLE, to understand this better first study the SJF algorithm from OS and then try this problem, it will be breeze to solve it...Hope it helps
class Solution {
public:
int maxEvents(vector& events) {
// introduce a timeline variable --> which will go from day 0 to day n
// this is done, because according to question an event spans through a number of days
// and we can attend this event anyday in between, so we will basically attend one event
// in one day, hence the timeline variable will tell us which event to attend on the particular
// day, also for maximum events we will sort the events based on their starting times
// and we will use the timeline variable to push those events into the set/pq which have
// arrived till that time, and attend the one having lower end time first and so on...
int n = events.size();
sort(begin(events), end(events));
int timeline = 0, index = 0;
int count = 0;
priority_queue minheap;
while(index < n || !minheap.empty()){
// edge case when large gap b/w events or start event
if(minheap.empty() && timeline < events[index][0]){
timeline = events[index][0];
}
// pick the events that have arrived till this timeline
while(index < n && events[index][0]
the time complexity if this solution is O(nlogn + n*d). It is possible to do it in O(nlogn + d)
how?
Thankyou bhaiya for this video
Good solution but you shouldn't take set here! It will increase time.
Its giving time limit exceeded on leet code
I am sorry. Now they have added larger cases.
@@mohammadfraz its giving wrong answer
Great explanation sir
Thanks
Please add more and more videos
Thanks bro
job sequencing algorithm
tnx bud
this code will give tle
Yes bro , they added cases.
C++ code:
bool static comp (vector & a, vector & b) {
if (a[1] < b[1]) return true; // sorting acc to end time
else if (a[1] == b[1]) return a[0] < b[0]; // sorting acc to start time if same end time
return false;
}
int maxEvents(vector& events) {
sort (events.begin(), events.end(), comp);
int count = 0;
set days;
for (int i = 1; i
poor explanation
very poor explanation. No intution no thinking
slightly better java solution
class Solution {
public int maxEvents(int[][] events) {
// sort the events array by the end date and if they are equal then by start date
Arrays.sort(events, new Comparator() {
public int compare(int[] a, int[] b) {
if (a[1] > b[1]) {
return 1;
} else if (a[1] == b[1]) {
if (a[0] > b[0]) {
return 1;
} else {
return -1;
}
} else {
return -1;
}
}
});
// initilization of vars
int counter = 0;
int start = 0;
int end = 1;
// find the max time and min time to fill the set
int max = 0;
int min = Integer.MAX_VALUE;
for (int row = 0; row < events.length; row++) {
max = max > events[row][end] ? max : events[row][end];
min = min < events[row][start] ? min : events[row][start];
}
// create set and fill it with true values, that signifies the days of the event which have not been visited. If false then it is visited
boolean[] set = new boolean[max-min+1];
for (int i = min; i
FOR THOSE GETTING TLE.
upper_bound(Set.begin(), Set.end(), x) is a function that doesn't know anything about std::set internal structure.
Set iterators are not random-access meaning that upper_bound has to perform O(n) iterator movements in order to access any position in the container.
That's why you should never use lower_bound/upper_bound with std::set
but you can use Set.lower_bound(x)/Set.upper_bound(x) that perform a search over a binary search tree, that works obviously in log n/
So basically use : days.lower_bound(s)
Reference: codeforces.com/blog/entry/22074
I was getting TLE using upper_bound(Set.begin(), Set.end(), x) and was wondering wtf is wrong. Surely got something super important to learn. Thanks mate!