You didn’t even need the k, i used a greedy approach as well and passed within time O(N).
Basically, my algo was as follows:
Sort the customers segregated by first the compartments, then by their arrival time. Hold one customer with us,start by the first customer :
- If the next customer needs a different slot(all requests for current slot is done) accept the one with us and hold on to the new one.
- Else, if the next customer arrives after the customer with us would leave - we can cater to the customer with us. So increment the count and hold the new customer now.
- Else, if the next customer can leave earlier than our current - shoo away the current and keep the new one.
Yes, DP is feasible for this problem. Congratulations for you Accept!
I think greedy is much easier to implement, since we don’t need to remap the times.
I have sometimes problem with greedy algorithms, because sometimes its not easy if it works or not…
Just a comment, in this specific case, the correctness of the greedy approach can be proven.
(cf. the linked wiki page about Activity Selection Problem)
I have implemented the same method and solution is accepted with 2.02s but I can see solution with similar approach accepted in less than 1s. Is it only because of the fast IO or some other tweak in the code ?
My solution : CodeChef: Practical coding for everyone
I used radix sort for sorting finishing time and preferred components, and then used the activity selection problem, coupled with fast I/O and got AC. Link: CodeChef: Practical coding for everyone
but is my approach correct and if it is how to implement it?
Vectors of vector is extremely time consuming for such large data. POD works better here.
Your struct is supposed to take 3 members at compile time, so it is faster. On the other hand, a vector is generic and ready to accommodate more elements (members) although you don’t supply it.
Plus vector keep track of currently allocated memory and size behind the scene that is more expensive than PODs(more@Passive data structure - Wikipedia) without any constructor/destructor cost.
@anonymousins read my answer above, I’ve used the same idea. When searching for hash functions I came across STL maps, read about them, implemented them in my code and voila! AC! 
STL map takes care of hasing, I read that its insert, delete and lookup operations are of O(logn) complexity.
Will you please help me checking why am I getting WA for the problem.
http://www.codechef.com/viewsolution/3256692
how can we do it in c?
I think it should be caused by different implementation. STL is always a little slower.
If you want to do it in C you’ll have to write your own code, but I suggest you start using C++ with STL, C++11 library is huge and its also the standard.
Shouldn’t it be dp[T]=max(dp[T+1],1+dp[L]); ??
hello 
the main differences I can see between both of our solutions is the type used to store the answer… I’ve used long long
EDIT: After changing the data types I now get TLE veredict with your code… Try to encapsulate the main procedure to get the answer on a separate function… It’s easier to debug and spot bottlenecks
I am struggling to find error in this code of mine from past 2 hours, it gives segmentation fault and I am not able to see any reason for that. Can anyone please help.
https://www.codechef.com/viewsolution/29699503
Thanks man! Changing K size array to a map get my solution accepted. 
https://www.codechef.com/viewsolution/31994049
I used a vector of priority queues to maintain the increasing order of the finishing times. Then I extracted the top and checked whether it overlaps with the previous interval. If not then I increase the count. Somehow I am getting a TLE message. I just want to know how can I further improve the efficiency.
Here’s my code: CodeChef: Practical coding for everyone
Any help would be appreciated.
Thank you
What is the problem with this solution? It is passing test cases but I am getting the wrong answer in hidden test cases. Someone, please help.
class Codechef
{
public static void SortArray(int[] arr, int[] depar,int[] pref,int n){
for(int i=0;i<n-1;i++){
if(arr[i]>arr[i+1]){
// sorting arrival time
int temp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
// sorting departure time
int dep=depar[i];
depar[i]=depar[i+1];
depar[i+1]=dep;
// sorting preferences array
int pre=pref[i];
pref[i]=pref[i+1];
pref[i+1]=pre;
}
}
}
public static void Apetite(int[] arr,int[] depar,int[] pref,int k, int n){
Map<Integer,Boolean> occupied = new HashMap<>();
int count=0,keep_in=-1;
for(int i=0;i<n;i++){
if(!occupied.containsKey(pref[i])){
occupied.put(pref[i],false);
}
if(!occupied.get(pref[i])){
count++; keep_in++;
occupied.replace(pref[i],true);
}else{
if(arr[i]>=depar[keep_in]){
count++; keep_in++;
}
}
}
System.out.println(count);
}
public static void main(String[] args) throws java.lang.Exception {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt(); int k=sc.nextInt();
int[] arr = new int[n]; int[] depar = new int[n];
int[] pref = new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt(); depar[i]=sc.nextInt();
pref[i]=sc.nextInt();
}
SortArray(arr,depar,pref,n);
Apetite(arr,depar,pref,k,n);
}
}