Interview Practice Round #1

Hello CodeDrills,
We are holding an interview practice round having 3 interview type problems.

Contest Details

Good Luck & Have Fun!
Hope to see you participating!!

4 Likes

Hii can someone point out why this code gives WA (for the 3rd problem - Maximum Job Profit), It gives WA at TC-9.

#include<bits/stdc++.h>
using namespace std;

const int N = 3e7;
long dp[N];
class JobProfit {
public:
	
	
	long getMaximumProfit(std::vector<int> startTime, std::vector<int> endTime, std::vector<int> profit) {
		
		long n = profit.size();
		
		if(n == 0){
			return 0*1ll;
		}
		
		if(n == 1){
			return profit[0]*1ll;
		}	
		
		vector<pair<pair<long,long>,long>> v;
		for(long i=0;i<n;i++){
			v.push_back({{startTime[i],endTime[i]},profit[i]});	
		}
		sort(v.begin(),v.end());
		
		for(long i=0;i<n;i++){
			dp[i] = v[i].second;
		}
		
		auto Bin = [&](long val){
			long l=val,r=n-1;
			long ans = -1;
			while(l <= r){
				
				long mid = (l+r)/2;
				if(v[mid].first.first >= v[val].first.second){
					ans = mid;
					r = mid-1;
				}
				else{
					l = mid+1;
				}
			}
			return ans;
		};
		
		long maxi = v[n-1].second;
		for(long i=n-2;i>=0;i--){
			
			maxi = max(maxi,v[i].second);
			long index = Bin(i); //find index greater than the end time of current index.
			if(index == -1){
				maxi = max(maxi,v[i].second);
			}
			else{
				long tot = dp[index];
				long val = tot + v[i].second;
				maxi = max(maxi,val);
			}
			dp[i] = maxi;
		}
		return maxi;
	}
};

2 Likes

Think when all arrays are empty :stuck_out_tongue:
You are trying

if n=0, v[-1] won’t exist hence RE.

3 Likes

Ohh thanx, can u just check if there’s some edge case missing coz I think my idea is somewhat up to the point, but it gives me WA-9

UPD: Ig it seems like I am having something wrong in sort function, I should have used the comparator, let me check that once

2 Likes