Do leave a comment if you get the solution :) helps me a lot C++ Code link: github.com/striver79/SDESheet/blob/main/NmeetingsCpp Java Code link: github.com/striver79/SDESheet/blob/main/NmeetingsJava Instagram: striver_79 Join our telegram group: t.me/Competitive_Programming_tuf
Just for a tip- if your comparator fn keep giving u something like this "invalid use of non-static member function", just use static infront of your comparator. Like this to let me know i wasn't alone in this
@@nikhild.20 its probably related to how comparator functions are defined in C++, static keyword permanenty allocated the memory for a function/datatype so that it cant be changes further
Without complicating much, a simple solution could be using vector of pairs. int maxMeetings(int start[], int end[], int n) { vector meet; for(int i=0; i
we can do the bool comparator function in a less confusing way - bool comparator(struct meeting m1, meeting m2) { return m1.end != m2.end ? m1.end < m2.end : m1.pos < m2.pos; } had a better conceptual clarity after watching your video, thanks man!
solution using a minimum heap(sorting according to the end array) int maxMeetings(int start[], int end[], int n) { priority_queue pq; for(int i=0;i last){ count++; last = x.first; } } return count; }
no need to use comparator in this fn, c++ sort does the job autmatically for u. Declare your vector like this. vector meetings; Each element inside this 2d vector is of this format : [{{endTime,index},startTime}] sort(meetings.begin(),meetings.end()); the sort fn will sort the array acc to end time first, if the end time of two activity is same, it will use the index or the order in which they appear to sort. int startTime = meetings[i][0].second; int endTime = meetings[i][0].first.first; int order = meetings[i][0].first.second;
Without creating that extra datastructure to store data just store pair of end value and index int maxMeetings(int start[], int end[], int n) { // Your code here pairpr[n+1]; //copying the ending time of meeting and sort according to its end time for(int i=0;i
Damn, when you made this video this problem had 6k submissions on gfg. Now its 22k. The amount of influence SDE sheet has on coding community is overwhelming.
@@iamnoob7593 bro now I am on dev side I don't do dsa anymore bcz it's a waste of time after 200- 300 question so I forgot what I commented 11 month ago, Btw I have solved 400 dsa question and I am better than striver in problem solving if u give me enough time to solve problem like 1 problem = 1 day
After little modification (defining static to comparator class Solution { public: //Function to find the maximum number of meetings that can //be performed in a meeting room. struct meeting { int start; int end; int pos; }; static bool comparator(struct meeting m1, meeting m2) { if (m1.end < m2.end) return true; else if(m1.end > m2.end) return false; else if(m1.pos < m2.pos) return true; return false; } int maxMeetings(int s[], int e[], int n) { struct meeting meet[n]; for(int i = 0;i
👏👏👏Kudos to you i got stuck at that point finally solution accepted in gfg. but one thing i doubt why we have to use static while defining comprator??🙄
//same approach //using pair int maxMeetings(int start[], int end[], int n) { int count = 1; //1. store start and end times in pair(end[i], start[i]) vector v; for(int i=0; i
Sir can you please explain more on the case where finishing time is the same like {3,8} {5,8} I mean in any case whoever comes first in the sorted array the answer is going to be the same. And I am not able to get that test case where it is giving an error in GFG. One more thing sir the below comparator was also giving correct answer: and here if you see {3,8} , {5,8} will be change to {5,8},{3,8} which is contradiction to your code but still both are giving correct answer. bool comparator(pairp1,pairp2) { if(p1.second
Coz in the above test case which strive used if (8,9) in pos 6 is before (8,9) in pos 4 in data structure then our output will be 1 3 5 6 and if (8,9) in pos 4 is before (8,9) in pos 6 then our output will be 1 3 5 4 which is correct
Can't this question be solved like minimum number of platforms wherein we sorted both the arrival and departure time arrays? If not, then how to judge where we can apply that concept and where we can't?
here you can skip some meetings and maintain only one room, but in train station, you cannot skip a train and have to increase stations count to store more trains
It seems there is no need to store their position at all simply use vector of pair to store the start and end time now sort them according to their end times then simply check whether next meeting's start is less than end of current one or not. int maxMeetings(int start[], int end[], int n) { vectorvec; for(int i=0;i
Why is this problem repeated in SDE Sheet? I mean firstly 'N meeting in one room' and now this, why 2 exactly same problems you've included @takeUforward ?
We can use approach like min platform for train problem, And print ans only when platform==1, Time nlogn Space 1 As we can perform thing on given array only
It's easier if we use priority queue (min heap) instead of comparators. Time complexity and space comp remains the same. This is my code int maxMeetings(int start[], int end[], int n) { // Your code here int count = 0; priority_queuepq; for(int i=0; iprevTime){ count++; prevTime = ending; } }while(!pq.empty()); return count; }
Like suppose (x1,y1) (x2,y2) (x3,y3) (x4,y4 ) are the intervals and y4>=y3>=y2>=y1, then how can we say that choosing a (x1,y1) is an optimal choice. Is there any mathematical proof of that
I tried this solution by converting this question same like activity selection problem and it got accepted bool sortbysec(const pair &a, const pair &b) { return (a.second < b.second); } class Solution { public: //Function to find the maximum number of meetings that can //be performed in a meeting room. int maxMeetings(int start[], int end[], int n) { vector vec(n); for(int i=0; i
Bhaiya if I use multimap instead of map will it be a problem? Like will it show laziness (in the interview perspective). Right now gfg has changed this question. Using map I cannot store similar keys, so used a multimap instead of making a vector and comparator and then sorting it. Loved the video. Excellent as always.
#define PIII pair class Solution { public: //Function to find the maximum number of meetings that can //be performed in a meeting room. int maxMeetings(int start[], int end[], int n) { vector vec; for(int i=0; i
Choosing the meeting whose Duration is shortest ( Many short meeting implies more small small meeting in given time thus maximising the number of meetings) . What's wrong with this ?
Suppose there are meeting with (start,end) as (1,7),(6,9),(8,15)... So if u will chose a/c to smallest duration...u will pick only (6,9) but with Intuition of "what's ends early should be picked first" will give us actual ans which is (1,7)and (8,15)in this case
Suppose there are meeting with (start,end) as (1,20) , (2,21). Duration wise both meeting are of length 19 and 19 . So your answer may be that both are possible, but since the first meeting is ending at 20, and next meeting has to start at 2, so it's not possible because room was occupied at 2 by first meeting
Ez implementation with vector of pairs. Make pairs of end time and start time for each meeting. End must be pushed first in the pair i.e.(end, start) because sort() method by default sorts according to first parameter AND WE WANT EXACTLY THAT! C++: int maxMeetings(int start[], int end[], int n) { vector times; for (int i = 0; i < n; i++) times.push_back({end[i], start[i]}); sort(times.begin(), times.end()); int ans = 1; //first meeting will be done no matter what int prevFinish = times[0].first; for (int i = 1; i < times.size(); i++) { int currStartTime = times[i].second; if (currStartTime > prevFinish) { prevFinish = times[i].first; ans++; } } return ans; }
bcz it has the least end time, so without thinking about its start, we can surely say that if it ended first it surely would've started first. Hope this clears your doubt
//using multimap int maxMeetings(int start[], int end[], int n) { // Your code here multimap me; for(int i=0;i las) { cnt++; las = el.first; } } return cnt; } is the way ok ?
Not got that much deep into that, saw some articles and got this, am also new to java! Learning for making videos only :) I make sure the C++ code is the cleanesst and optimal, and then just replicate to java with the help of google XD
what about the case if s[i] is somewhat like 1,0,7 and f[i] is like 5,6,9 then output should be both 1 3 and 2 3 but the algorithm would only output 1 3 while 2 3 is also correct , so what to do about that?
2 3 is not correct because the first meeting happening is starting at 1 and ending at 5, so another meeting cannot start at 0 because the time has passed and now any meeting which wants to start will start after 5 only
code for updated problem if anyone needs :) struct myType { int s; int e; }; static bool myComp(myType x, myType y) { if(x.e == y.e) return x.s < y.s && x.e == y.e; return x.e < y.e; } //Function to find the maximum number of meetings that can //be performed in a meeting room. int maxMeetings(int start[], int end[], int n) { // Your code here vector meets(n); for(int i=0;i
Let's say we sorted on the basis of starting time, then we'll have (0,6,2) before (1,2,1) which will block the room for most of the meetings since the end time is very big. So end time is the deciding factor to sort since we need to schedule maximum number of meetings in the room.
Why the SC is O(n) and not O(3n) as we are storing three different values for each input or it's O (n) bcoz we are just storing inputs + there index and the index part is only considered??
Nice explanation. I've a question here. Please help me understand. Would it really cause any issue if i sort the array based on the meeting start time?
I did it with recursion, but the answer is wrong. Can anyone help ? int helper(int start[], int end[], int i, int n, int prev){ if(i == n) return 0; int temp1 = 0, temp2 = 0; temp1 = helper(start, end, i+1, n, prev); if(prev==-1 || prev
FYI : If you are getting this error :- (error: non-static variable this cannot be referenced from a static context) THEN Remove the "static" keyword from "maxMeetings" function .
Well I solved it using a priority queue instead of sorting it the complexity is same and we could do everything easily with it. Is there any flaw with that....??
How can we find out when to sort based on starting time and finishing time for these kind of greedy problems?Any logic for finding out this.Cant we do this problem optimally if we sort based on starting time?
You can use Comparable interface also -> static class Pair implements Comparable { int start; int end; Pair(int start, int end) { this.start = start; this.end = end; } public int compareTo(Pair o) { return this.end - o.end; } } public static int maxMeetings(int[] start, int[] end, int n) { PriorityQueue pq = new PriorityQueue(); for (int i = 0; i < n; i++) { pq.add(new Pair(start[i], end[i])); } int c = 1; int ed = pq.poll().end; while (!pq.isEmpty()) { Pair p = pq.poll(); if (p.start > ed) { c++; ed = p.end; } } return c; }
should it be not meet.get(i).start > = limit if in case we have end time of previous meeting equal to start time of other or are we taking assumption meeting won't start or end same time?
Posting python solution if any one wants to checkout : def maximumMeetings(self,n,start,end): # create array which can store start and end time pairs arr = [] for i in range(len(start)): arr.append([start[i], end[i]]) # sort new array based on finish time arr.sort(key=lambda x: x[1]) # last finish time lf = -1 # total meeting can be held total = 0 for s, f in arr: # if next meeting start anytime last meeting finishes if s > lf: # update total meeting total += 1 # update last finish time lf = f return total
class Solution { public: // Function to find the maximum number of meetings that can // be performed in a meeting room. static bool compare(pair &a, pair &b) { if (a.second < b.second) return true; if (a.second > b.second) return false; return a.first < b.first; } int maxMeetings(int start[], int end[], int n) { // Your code here int c = 1; vector v; for (int i = 0; i < n; i++) v.push_back({start[i], end[i]}); sort(v.begin(), v.end(), compare); int limit = v[0].second; for (int i = 1; i < n; i++) { if (v[i].first > limit) { limit = v[i].second; c++; } } return c; } };
Bhya, thank you for making videos daily, use to wait for your videos like hell every day, and your way of explanation for java code, ummmaahhhh💥😍😍, mza aa gya
why does it work without having the tie condition in the sorting compare function, I had the same confusion, Do we need to include this condition? In basic sorting even if they are equal the greater index will come later so it will be put later in the sorted array by default.
Yeah. This problem doesn't need a comparision for tie condition. But ig in a more practical environment, meeting id's matter. So thats why he probably used it. Regardless, it was unnecessary for solving this particular problem.
The video's comparator function can also be written as below -> bool comp (meeting &a , meeting &b){ if(a.end != b.end){ return a.end < b.end; } return a.pos < b.pos; };
Hey Bhai.. I have to ask you something.. I got selected in TCS on a java language only and didn't know anything about DS, Algorithm and CP.. But if I work on these topics So after 1-2 year Can I get a job in product base companies.. And also tell how to start? Must Reply plzzzzzzzz
Hi Striver. Great video. Just a query, instead of using struct, had used vector and stored in the fashion {startTime, endTime, pos}. However, using this, it was getting TLE while as soon as I replaced with struct, it ran easily. Why is it so? Can anyone please answer this?
@@sourabhbhattacharya2577 I hope you would have figured out a solution but I saw that if you pass by reference to the comparator function then there would be no TLE.
Please tell me while solving recursive/dp/graph problems on leetcode, can we use extra method of our own or just the already given one with the given number of parameters only? Is using another function with different parameters restricted in interview?
@@takeUforward sorry sir may be you told it in java solution i see only c++ solution after explanation but thank you so much sir for your great effort 😊
How to sort without using sort() method in this code ... Please reply anyone class MeetComparator implements Comparator { public int compare (Meet m1 , Meet m2){ if(m1.end > m2.end) return 1; else if (m1.end
But we want to have maximum number of meetings, so we sort them and do choose according to finish times. Even if it appears first, on sorting it will go back.
Do leave a comment if you get the solution :) helps me a lot
C++ Code link: github.com/striver79/SDESheet/blob/main/NmeetingsCpp
Java Code link: github.com/striver79/SDESheet/blob/main/NmeetingsJava
Instagram: striver_79
Join our telegram group: t.me/Competitive_Programming_tuf
class Meeting {
public static int maxMeetings(int start[], int end[], int n) {
ArrayList meet=new ArrayList();
for(int i=0;i
Your code is not passing on GFG
@@PRABHATKUMAR-ox6jw yes . there's problem in
sort(meet,meet+n,comparator); line it shows like that
Just for a tip- if your comparator fn keep giving u something like this "invalid use of non-static member function", just use static infront of your comparator. Like this to let me know i wasn't alone in this
It worked!!!! Thanks. But, can you tell what is this about? I mean what's the reason we were getting this error?
@@nikhild.20 its probably related to how comparator functions are defined in C++, static keyword permanenty allocated the memory for a function/datatype so that it cant be changes further
@Ayush Negi Thanks!
Without complicating much, a simple solution could be using vector of pairs.
int maxMeetings(int start[], int end[], int n)
{
vector meet;
for(int i=0; i
Good one
thanks!
This way it's damn simple.Thanks!!
I had been struggling for so long but now I am finally able to grasp the algorithm. Thanks a bunch!!
Seeing that you have created a video on a particular topic makes me feel so good that ok now I'm going to understand this completely!!
we can do the bool comparator function in a less confusing way -
bool comparator(struct meeting m1, meeting m2)
{
return m1.end != m2.end ? m1.end < m2.end : m1.pos < m2.pos;
}
had a better conceptual clarity after watching your video, thanks man!
solution using a minimum heap(sorting according to the end array)
int maxMeetings(int start[], int end[], int n)
{
priority_queue pq;
for(int i=0;i last){
count++;
last = x.first;
}
}
return count;
}
no need to use comparator in this fn, c++ sort does the job autmatically for u.
Declare your vector like this.
vector meetings;
Each element inside this 2d vector is of this format : [{{endTime,index},startTime}]
sort(meetings.begin(),meetings.end());
the sort fn will sort the array acc to end time first, if the end time of two activity is same, it will use the index or the order in which they appear to sort.
int startTime = meetings[i][0].second;
int endTime = meetings[i][0].first.first;
int order = meetings[i][0].first.second;
5:20 the reason why most people prefer leetcode over gfg for interview preparation
leetcode compares your tc and sc with other submissions, while gfg just show your time vs total time allowed.
@@ayushbari7174leetcode's runtime and memory varies.
Without creating that extra datastructure to store data just store pair of end value and index
int maxMeetings(int start[], int end[], int n)
{
// Your code here
pairpr[n+1];
//copying the ending time of meeting and sort according to its end time
for(int i=0;i
Damn, when you made this video this problem had 6k submissions on gfg. Now its 22k. The amount of influence SDE sheet has on coding community is overwhelming.
now it's 74.8K
@@lalithsai5392 now it's 150k
@@dillirajtimalsina now?
@@iamnoob7593 bro now I am on dev side I don't do dsa anymore bcz it's a waste of time after 200- 300 question so I forgot what I commented 11 month ago,
Btw I have solved 400 dsa question and I am better than striver in problem solving if u give me enough time to solve problem like 1 problem = 1 day
@@dillirajtimalsina you still cant be
After little modification (defining static to comparator
class Solution
{
public:
//Function to find the maximum number of meetings that can
//be performed in a meeting room.
struct meeting {
int start;
int end;
int pos;
};
static bool comparator(struct meeting m1, meeting m2)
{
if (m1.end < m2.end) return true;
else if(m1.end > m2.end) return false;
else if(m1.pos < m2.pos) return true;
return false;
}
int maxMeetings(int s[], int e[], int n) {
struct meeting meet[n];
for(int i = 0;i
👏👏👏Kudos to you i got stuck at that point finally solution accepted in gfg.
but one thing i doubt why we have to use static while defining comprator??🙄
Thanks ! , it worked ..
//same approach
//using pair
int maxMeetings(int start[], int end[], int n)
{
int count = 1;
//1. store start and end times in pair(end[i], start[i])
vector v;
for(int i=0; i
Thanks buddy🤗
Sir can you please explain more on the case where finishing time is the same like {3,8} {5,8} I mean in any case whoever comes first in the sorted array the answer is going to be the same. And I am not able to get that test case where it is giving an error in GFG.
One more thing sir the below comparator was also giving correct answer:
and here if you see {3,8} , {5,8} will be change to {5,8},{3,8} which is contradiction to your code but still both are giving correct answer.
bool comparator(pairp1,pairp2)
{
if(p1.second
Iif end time of any two meetings are same why do we need sort on basis of position ? Why it will given wrong answer if not taken care of position ?
same doubt
I solved without that condition on gfg , it got submitted without errors
Coz in the above test case which strive used if (8,9) in pos 6 is before (8,9) in pos 4 in data structure then our output will be 1 3 5 6 and if (8,9) in pos 4 is before (8,9) in pos 6 then our output will be 1 3 5 4 which is correct
Can't this question be solved like minimum number of platforms wherein we sorted both the arrival and departure time arrays? If not, then how to judge where we can apply that concept and where we can't?
here you can skip some meetings and maintain only one room, but in train station, you cannot skip a train and have to increase stations count to store more trains
It seems there is no need to store their position at all simply use vector of pair to store the start and end time now sort them according to their end times then simply check whether next meeting's start is less than end of current one or not.
int maxMeetings(int start[], int end[], int n)
{
vectorvec;
for(int i=0;i
Can someone explain the Logic behind sorting according to end times?
@@anubhavs5145 because next meeting can start only after the current one ends.
No need to maintain order I wrote this comparator and it worked fine for me
bool myCmp(pairp1,pairp2){
return p2.second>p1.second;
}
Why is this problem repeated in SDE Sheet? I mean firstly 'N meeting in one room' and now this, why 2 exactly same problems you've included @takeUforward ?
I sorted the starting time
// Sort
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int maxMeetings(int start[], int end[], int n) {
vector timings;
for(int i = 0; i < n; i++) timings.push_back({start[i], end[i]});
sort(timings.begin(), timings.end());
int res = 1, end_time = timings[0].second;
for(int i = 1; i < n; i++) {
if(end_time >= timings[i].first) {
end_time = min(end_time, timings[i].second);
} else {
res++;
end_time = timings[i].second;
}
}
return res;
}
};
{{0,10} , {1,2} , {3,4} , {5,6}}
Herw we can schedule 3 meetings :)
sesky sesky sesky same thought process same solution
Problem Solving is like striver is exceptional at least for me😊💯
U r awesome 👍🏻
We can use approach like min platform for train problem,
And print ans only when platform==1,
Time nlogn
Space 1
As we can perform thing on given array only
It's easier if we use priority queue (min heap) instead of comparators. Time complexity and space comp remains the same.
This is my code
int maxMeetings(int start[], int end[], int n)
{
// Your code here
int count = 0;
priority_queuepq;
for(int i=0; iprevTime){
count++;
prevTime = ending;
}
}while(!pq.empty());
return count;
}
Like suppose (x1,y1) (x2,y2) (x3,y3) (x4,y4 ) are the intervals
and y4>=y3>=y2>=y1,
then how can we say that choosing a (x1,y1) is an optimal choice. Is there any mathematical proof of that
Striver y don't you provide python code as well i usually take references of ur c++ code but this one was complex.
I tried this solution by converting this question same like activity selection problem and it got accepted
bool sortbysec(const pair &a,
const pair &b)
{
return (a.second < b.second);
}
class Solution
{
public:
//Function to find the maximum number of meetings that can
//be performed in a meeting room.
int maxMeetings(int start[], int end[], int n)
{
vector vec(n);
for(int i=0; i
i used same approach and it worked
Bhaiya if I use multimap instead of map will it be a problem? Like will it show laziness (in the interview perspective). Right now gfg has changed this question. Using map I cannot store similar keys, so used a multimap instead of making a vector and comparator and then sorting it.
Loved the video. Excellent as always.
#define PIII pair
class Solution
{
public:
//Function to find the maximum number of meetings that can
//be performed in a meeting room.
int maxMeetings(int start[], int end[], int n)
{
vector vec;
for(int i=0; i
Choosing the meeting whose Duration is shortest ( Many short meeting implies more small small meeting in given time thus maximising the number of meetings) . What's wrong with this ?
Suppose there are meeting with (start,end) as (1,7),(6,9),(8,15)...
So if u will chose a/c to smallest duration...u will pick only (6,9) but with Intuition of "what's ends early should be picked first" will give us actual ans which is (1,7)and (8,15)in this case
Suppose there are meeting with (start,end) as (1,20) , (2,21).
Duration wise both meeting are of length 19 and 19 .
So your answer may be that both are possible, but since the first meeting is ending at 20, and next meeting has to start at 2, so it's not possible because room was occupied at 2 by first meeting
Ez implementation with vector of pairs. Make pairs of end time and start time for each meeting. End must be pushed first in the pair i.e.(end, start) because sort() method by default sorts according to first parameter AND WE WANT EXACTLY THAT!
C++:
int maxMeetings(int start[], int end[], int n) {
vector times;
for (int i = 0; i < n; i++) times.push_back({end[i], start[i]});
sort(times.begin(), times.end());
int ans = 1; //first meeting will be done no matter what
int prevFinish = times[0].first;
for (int i = 1; i < times.size(); i++) {
int currStartTime = times[i].second;
if (currStartTime > prevFinish) {
prevFinish = times[i].first;
ans++;
}
}
return ans;
}
It would be of great help if you could please tell me why are we always selecting 1st activity in the beginning without any test cases failing.
bcz it has the least end time, so without thinking about its start, we can surely say that if it ended first it surely would've started first. Hope this clears your doubt
//using multimap
int maxMeetings(int start[], int end[], int n)
{
// Your code here
multimap me;
for(int i=0;i las)
{
cnt++;
las = el.first;
}
}
return cnt;
}
is the way ok ?
is comparator function in java completely opposite to that in c++ (in terms of -1/1 and false/true)?
Not got that much deep into that, saw some articles and got this, am also new to java! Learning for making videos only :) I make sure the C++ code is the cleanesst and optimal, and then just replicate to java with the help of google XD
what about the case if s[i] is somewhat like 1,0,7 and f[i] is like 5,6,9 then output should be both 1 3 and 2 3 but the algorithm would only output 1 3 while 2 3 is also correct , so what to do about that?
both are acceptable, motive is just to get maximum meetings to be conducted
2 3 is not correct because the first meeting happening is starting at 1 and ending at 5, so another meeting cannot start at 0 because the time has passed and now any meeting which wants to start will start after 5 only
Problem is updated now,
U should declare comparator function as
static bool comparator (. )
Other u will get error as invalid use of static variable
Thankyou buddy, just looking for this.
Thank you bro
can you tell why its required to use static???
code for updated problem if anyone needs :)
struct myType
{
int s;
int e;
};
static bool myComp(myType x, myType y)
{
if(x.e == y.e)
return x.s < y.s && x.e == y.e;
return x.e < y.e;
}
//Function to find the maximum number of meetings that can
//be performed in a meeting room.
int maxMeetings(int start[], int end[], int n)
{
// Your code here
vector meets(n);
for(int i=0;i
Hey Striver !! Please could you provide explanation on what criteria we have chosen to sort on basis of "end Time" , not other combinations.
Let's say we sorted on the basis of starting time, then we'll have (0,6,2) before (1,2,1) which will block the room for most of the meetings since the end time is very big. So end time is the deciding factor to sort since we need to schedule maximum number of meetings in the room.
Can we do this by sorting the meetings by the start time in ascending order then ..??
Why the SC is O(n) and not O(3n) as we are storing three different values for each input or it's O (n) bcoz we are just storing inputs + there index and the index part is only considered??
O(3n) = O(n) bcz 3 is a constant number.
class Solution
{
public static int maxMeetings(int start[], int end[], int n)
{
return recursion(start,end,0,n-1,0);
}
static int recursion(int start[],int end[],int job_index,int n,int curr_time){
if(job_index==n){
if(start[job_index]>curr_time){
return 1;
}
return 0;
}
int take_meet=0;
if(start[job_index]>curr_time){
take_meet=1+recursion(start,end,job_index+1,n,end[job_index]);
}
int skip_meet=recursion(start,end,job_index+1,n,curr_time);
return Math.max(take_meet,skip_meet);
}
}
Can any one explain to me why this approach doesn't work?
Nice explanation. I've a question here. Please help me understand. Would it really cause any issue if i sort the array based on the meeting start time?
that will not work as you want to perform maximum no of meetings. So for that you should have to choose the meeting with smaller ending time.
can we use a min heap with key as finishing time , no need to sort it then it will automatically sort on the basis of key?
absolutely
I did it with recursion, but the answer is wrong. Can anyone help ?
int helper(int start[], int end[], int i, int n, int prev){
if(i == n)
return 0;
int temp1 = 0, temp2 = 0;
temp1 = helper(start, end, i+1, n, prev);
if(prev==-1 || prev
FYI : If you are getting this error :- (error: non-static variable this cannot be referenced from a static context) THEN
Remove the "static" keyword from "maxMeetings" function .
i get this error but maxmeetings does'nt have static variable
Well I solved it using a priority queue instead of sorting it the complexity is same and we could do everything easily with it. Is there any flaw with that....??
How can we find out when to sort based on starting time and finishing time for these kind of greedy problems?Any logic for finding out this.Cant we do this problem optimally if we sort based on starting time?
We only need to sort by end times. We don't need to add a condition for start times. It doesn't matter.
A condition for index has been added, without that the code gives wa in gfg. You can try submitting
@@takeUforward oh right, my bad. A note has been added at the bottom!
You can use Comparable interface also ->
static class Pair implements Comparable {
int start;
int end;
Pair(int start, int end) {
this.start = start;
this.end = end;
}
public int compareTo(Pair o) {
return this.end - o.end;
}
}
public static int maxMeetings(int[] start, int[] end, int n) {
PriorityQueue pq = new PriorityQueue();
for (int i = 0; i < n; i++) {
pq.add(new Pair(start[i], end[i]));
}
int c = 1;
int ed = pq.poll().end;
while (!pq.isEmpty()) {
Pair p = pq.poll();
if (p.start > ed) {
c++;
ed = p.end;
}
}
return c;
}
i wasn't able to solve it through comparator,thx buddy for the soln
should it be not meet.get(i).start > = limit if in case we have end time of previous meeting equal to start time of other or are we taking assumption meeting won't start or end same time?
Posting python solution if any one wants to checkout :
def maximumMeetings(self,n,start,end):
# create array which can store start and end time pairs
arr = []
for i in range(len(start)):
arr.append([start[i], end[i]])
# sort new array based on finish time
arr.sort(key=lambda x: x[1])
# last finish time
lf = -1
# total meeting can be held
total = 0
for s, f in arr:
# if next meeting start anytime last meeting finishes
if s > lf:
# update total meeting
total += 1
# update last finish time
lf = f
return total
Can't we use stable_sort in cpp without taking position in the vector???
class Solution
{
public:
// Function to find the maximum number of meetings that can
// be performed in a meeting room.
static bool compare(pair &a, pair &b)
{
if (a.second < b.second)
return true;
if (a.second > b.second)
return false;
return a.first < b.first;
}
int maxMeetings(int start[], int end[], int n)
{
// Your code here
int c = 1;
vector v;
for (int i = 0; i < n; i++)
v.push_back({start[i], end[i]});
sort(v.begin(), v.end(), compare);
int limit = v[0].second;
for (int i = 1; i < n; i++)
{
if (v[i].first > limit)
{
limit = v[i].second;
c++;
}
}
return c;
}
};
Bhya, thank you for making videos daily, use to wait for your videos like hell every day, and your way of explanation for java code, ummmaahhhh💥😍😍, mza aa gya
why does it work without having the tie condition in the sorting compare function, I had the same confusion, Do we need to include this condition? In basic sorting even if they are equal the greater index will come later so it will be put later in the sorted array by default.
Yeah. This problem doesn't need a comparision for tie condition. But ig in a more practical environment, meeting id's matter. So thats why he probably used it. Regardless, it was unnecessary for solving this particular problem.
The video's comparator function can also be written as below ->
bool comp (meeting &a , meeting &b){
if(a.end != b.end){
return a.end < b.end;
}
return a.pos < b.pos;
};
Why can't we use vector instead of struct??
Solution is fine but can you provide its proof od correctness?
exactly it makes no sense to explain intuition in 20 seconds and code in 20 minutes
bro really nice vids !! gr8 going
Glad you like them!
bool compare(pair &x, pair &y) {
return x.second < y.second;
}
int maximumMeetings(vector &start, vector &end){
vector pairs;
for(int i=0; i prevend){
cnt++;
prevend = x.second;
}
}
return cnt;
}
@14:30 can we use class instead of struct?
I performed this in c++ using same approach but using
Vectorv
Its giving same ans is it ok 🥺🥺
yeah, it's the same.
bhaiya Projects Dekh Dekh Kar bnaye hai courses se to koi issue hai?
i didnt knew about comparator , also i see we can use .sort() in different ways , even in mergesort we did something like this
2:52
Hey Bhai.. I have to ask you something..
I got selected in TCS on a java language only and didn't know anything about DS, Algorithm and CP..
But if I work on these topics So after 1-2 year Can I get a job in product base companies.. And also tell how to start?
Must Reply plzzzzzzzz
1 year is more than enough.Be consistent in the journey. You will get it for sure
Which college you are placed in TCS
I tried doing the same using vector but it is giving me TLE. Can't figure it out why its happening😕
yes bro it will give TLE use vector
used pair of pair of vector instead ..
class Solution
{
public:
static bool comparator(const pair &a,const pair &b)
{
if(a.second.firstb.second.first) return false;
else if(a.second.second
sometimes i forget to like ,so i specially come backs to like yr videos
@take U forward, bhya why we use @Override, we can't do without that....?
Since we are implementing something which has a similar function name, we have to override it.
@@takeUforward thank you bhya, got it 💓😍, aap pura fit ho jaiye jldi se, backtracking wale day me jyada problem ho ri h 🤕
💯💯💥💥🔥🔥 Happy new year Striver 🙏🙏
why does this work?
Why does the lower position meeting has to appear first in our data st if ending time is same?
The one that appeared first is served first so that in this case too
I think this is somewhat similar to activity selection problem.
The output in the given question link only shows number of output, not the indexes, index wale question ka link khha milega
They have recently changed it, when I recorded the video, it was having the index only.
@@takeUforward OK, CHALEGA, AB SACH MAI EASY HO GYA...LOL
Hi Striver. Great video. Just a query, instead of using struct, had used vector and stored in the fashion {startTime, endTime, pos}. However, using this, it was getting TLE while as soon as I replaced with struct, it ran easily. Why is it so? Can anyone please answer this?
does it take more time to sort vector of vectors instead of array of structs?
@@sourabhbhattacharya2577 I hope you would have figured out a solution but I saw that if you pass by reference to the comparator function then there would be no TLE.
Anyone from #JGEC
hey i am not able to locate the video in which he has taught about comparators.....can somebody plz provide the lin..!!thanks in advance
C++ stl video on channel
Can we solve this problem using a max heap?
Please tell me while solving recursive/dp/graph problems on leetcode, can we use extra method of our own or just the already given one with the given number of parameters only? Is using another function with different parameters restricted in interview?
yes you can
thanks buddy for such an easy way of explaining!
Liked it before watching
Thank You So Much for this wonderful video..............🙏🙏🙏🙏🙏🙏
How 0,6 is on the third leat time taking meeting..??
problem is different in GFG, why??
they changed it ..
Please share the link of python code.
their is no need to store answer in a vector we can print it directly
I m not sure if you saw the video completely, i told this in the video that m just doing to keep the logic part clean.
@@takeUforward sorry sir may be you told it in java solution i see only c++ solution after explanation but thank you so much sir for your great effort 😊
@@sahilgoyals great, cheers mate 🤟🏼 thanks for watching
Please continue keep making this series🙏
please continue the series!!
What is the TC and SC for this????
How to sort without using sort() method in this code ... Please reply anyone
class MeetComparator implements Comparator {
public int compare (Meet m1 , Meet m2){
if(m1.end > m2.end) return 1;
else if (m1.end
can we use LIS (DP) method to solve this?
Is in this question there is no overlapping sub problem if meeting are equal we are simply ordering them on basis of thier finishing time.
Understood.
Thanks a lot Striver !
Suppose if 0,6 meeting appear first then
But we want to have maximum number of meetings, so we sort them and do choose according to finish times. Even if it appears first, on sorting it will go back.
Ok that's not problem thank you
Day 8
I understood the intuition and code!
my nigga
Can u share link of comparator video
C++ stl on my channel
Understood!
Nice approach
Understood
superb explanation!!!
comparator video: ua-cam.com/video/RRVYpIET_RU/v-deo.html