This is an interval scheduling problem, isn’t it?
1 Like
Maybe yes… 
1 Like
Well … this is not difficult … when you know which algorithm to use!
If you do not it and try to find it, it is difficult ! I tried “fewer conflicts” and “shortest interval” before reading this forum and look for litterature on Google …
Hi there, is there any reason why in C++ this problem only has three test cases ? I think I might have a solution, but the last test case fails due to too large processing time.
My sorting method is basic (although I’m surprised that even this basic sorting method takes too long), and can probably be optimised, but I wouldn’t mind a couple of intermediary test cases to get a better idea of the improvements I need to make. Unless sorting isn’t required ?
2 Likes
What’s the time complexity of your sort? Do you use the builtin sort method?
I tried both a hand-coded basic bubble sort and a hand-coded basic selection sort. But I think I probably didn’t choose the right structures and operations for the problem. I’ve solved it now (using the std::sort method), but I still feel three test cases isn’t enough.
1 Like
3 test cases is not enough, yes. That’s an old puzzle, we tried to provide more test cases now.
The time complexity of bubble sort and selection sort is O(n^2) which was too slow.
3 Likes
Well that was easy. Five minutes of implementation and it was through. Gotta be greedy.
Pretty easy problem when you’re looking in the right direction. 10 minutes for the first two test cases, 10 more minutes to realize that recursivity is completely useless and pass the third test.
I mapped the durations to their starting day which avoids me to sort any vector. I don’t think it’s much more efficient but it’s much more simple to implement.
Solved in C++
Why in my puzzle page I got only 3 test cases?
Example 1
Example 2
Large number of scientists
while in the final page when I submit my solution I am getting :
Simple Case
One scientist
All starting days are identical
All end dates are identical
Parallel calculations
Overlapping calculations
Large number of scientists
Large number of satisfied scientists
The thing is I pass all three tests on the puzzle page. But when I submit my solution I get only 87% and a statement that last test “Large number of satisfied scientists” not passed.
1 Like
Validators are not the same as IDE tests. Your code is probably not optimized enough for the last validator test.
I make a habit of reading the forum before attempting the puzzles.
The solution was not obvious to me, though the coding was very easy, like 20 lines of C#.
This is one of my fastest solved Hard puzzles.
I am having an issue when I submit; my code fails all the “easy” validators, but passes most of the “hard/complex” validators. In the IDE, my code works just fine for the simpler examples (I suspect an “off by one error”, but how to tell?). How does one debug the validators? From a learning perspective, the disconnect between the IDE tests and the validators is a bit annoying.
Any suggestions for how to debug “Large number of scientists”? That is a stumbling block for me at the moment. My answer is about 487 too few. My algorithm works fine for the other validators, and even though I have duplicated the IDE test in jsfiddle, I am not exactly sure how to walk through 99999 entries. 
1 Like
Hello,
I have a little doubt on the solution of this problem.
Is it asked to give the highest number of runnable jobs but with an highest priority for the first to start (so we just need to check the jobs with the same start in fact).
Or is it asked to give the highest number of runnable jobs finally.
At first, i thank it was the second question but, even if I got a speed fast enough, my answer was really to high for the “correct” answer (~16xxx if i remember correctly, i can recheck it if you want).
Finally i did a ‘dumb’ algo to answer my first hypothetic question, and I got the correct answer on the 3 test.
Do i misundesrtand the question in this puzzle ?
Sorry for the baaad english ^^
If i understand your question correctly it’s the second version that is asked here.
There is no priority assigned to the jobs and each of them count as 1. As long as they don’t overlap, you can pick any combination you want. The answer is the number of jobs in the combination where the biggest number of jobs can run without overlapping.
Ah i’m sorry.
I re-think the principe and the question :i don’t even know how i get to have this problem in my mind…
Never prog when you’re tired.
Thanks anyway ^^
This problem was extremely easy. All you need to do is to find a (a pretty obvious) heuristic and voila, it`s done.
I think it should be moved in the medium section, but I don`t know what is the classification method.
As it seems, easy/medium problems are more about raw manipulations, without programing tehniques like backtracking/DP/Divide/greedy/B&B.
A big hint is in the categorization of the puzzle “greedy algorithms” - there is a simple, elegant solution that performs very well for the largest test cases. If you’re still stuck, research “Activity Selection Problem”.
10 Likes
I believe someone should switch test cases with the validators on “Super Computer” puzzle.
Currently there are only 3 tests available:
But plenty of Validators:
3 Likes