Activity Selection Problem - Greedy Algorithm | C++ Placement Course | Lecture 33.3

Notes of this Lecture:

[learningoverflow]

we can just save the end first and then start and then use normal sort function
for(int i=0;i<n;i++){
int start, end;
cin>>start>>end;
v.push_back({end, start});
}
sort(v.begin(), v.end());
please correct me if i am wrong

[sameerraj]

Rather than making a custom comparator just use vectors of pair and fill end time before the start and simply use the sort function.

[shivjyotigarai]

In 1:33, the output should be 1 rather than 2. Its said that "Start time of one chosen meeting can't be equal to the end time of the other chosen meeting."

[utkarshgautam]

how this guy is even teaching, leave it man, not for u, just blindly reading code

[AryanSharma-zljf]

anyone else with me who vibes on initial background music of apna college 😂😂😂

[anoopsaxena]

I sorted by end-start time, and then use the same concept as if( end<=activity[i][start] ) then take++; end=activity[i][end] ; is this sorting aprroach correct w.r.t to the original question? by considering their difference of duration, i assume to take those tasks with less duration and thus maximizing final ans.

[arpit]

Please share similar problems as well.

[sahajpatel]

jaldi se jaldi leni hai jo jaldi khatam ho rhi hai 😆 3:46

[thecaptaman]

Web development ka course continue nhi ho rha aur c++ ka course khatm nhi ho rha

[manishmalhotra]

Can be suggest this approach is correct or not.
Pseudo code
Take vector of pair
Sort with their starting time
Prevend=vector.second
Take=1
Loop(1->n)
If vector.first >=Prevend then
Take++
Prevend=vector.second.
Basically my logic is that choose those activity which start first and you can choose those activity whose starting time is equal or more than ending time of previous activity.

[albinthomas]

Bhai jaldi karna hai toh difference between start and end time kyo nahi dekhte hai joh kaam chota hoga usee jyaada hopayenge na

[upasanapan]

custom operator wala trick thick se samajh nhi aa rha hai

[ritik]

Upcoming premier are khatarnak 🤩🤩but i want to learn theae in java only please explain java code also

[VAIBHAVMALHOTRA]

Am I the only one who was dancing on those intro beats?

[MANPREETSINGH-fthd]

why we are using a[1] and b[1] in comparator, not a[0] and b[0] please someone explain.

[abhishekrajora]

sir code which you written this is wrong because if end time same in that case we have to check the first time that's why

[punitmaheshwari]

Jonsi = jo bhi ....Hindi bhi shi ho jayegi isse toh

[abhishekrajora]

sorry it was a right code it's my mistaken

[gogi-tech]

Sir I'm beginner which is best for me Android development or full stack web development? I have some basic knowledge html and css.
Plz reply 🙏? I want work from as freelancer.

[adarshraj]

typedef pair<int, int> pair1;

struct comp {
bool operator()(const pair1 &x, const pair1 &y) const {
if (x.second != y.second) {
return x.second < y.second;
}

return x.first < y.first;
}
};


int Solution::solve(vector<int> &A, vector<int> &B) {
vector<pair1>arr;
for(int i=0;i<A.size();++i)
{
arr.push_back({A[i], B[i]});
}
sort(arr.begin(), arr.end(), comp());
int take=1;
auto end=arr[0].second;
for(int i=1;i<A.size();++i)
{
auto temp=arr[i];
if(temp.first>=end)
{
take++;
end=temp.second;
}
}
return take;
}