DAGs and DP: aka one thing I'm good at and another that I'm not

So I haven't solved an SPOJ problem in a while. Mainly because I've been doing other things. Well today the drought is over. I managed to solve RENT.

I'll just describe how I went about solving this one. I should mention that the idea was not totally mine. Anyway, I will assume that you have either read the problem or are familiar with it's statement.

Well first off there is the obvious O(2^n) algorithm but obviously this is out of the question considering that the program has 3s to run and n can be as large as 10000. So the next thing to try is looking for a DP solution. This is where DAGs (Directed Acyclic Graphs) come into play, though it might not be obvious.

You construct the graph in the following way. There is an edge between vertex U and vertex V if there is an even starting at time U and ending at time V. Also the weight of the edge is equal to the amount of money you will get for selecting that activity. At this point you execute the DP portion by using a variation of a DFS (So as to not spoil the problem completely I'll let you figure that part out yourself). Just remember that you are looking to make the MOST money in the alloted time.

This method is O(E+V) once you have created your graph. I think the way I created my graph is close to O(E). With a few optimizations the above will work (at least in C++), my solution finished in 1.71s so if you are using Java or another language that isn't particularly "fast" some additional tweaks (or a completely different algorithm) might be necessary. I would like to mention that there are other methods to solve this problem but I didn't find them to be quite is intuitive or obvious. Plus I like working with graphs, and thought that transforming this into a graph problem was rather interesting.

EDIT: Now I also want to edit my algorithm so that it will also tell you which events to select. I don't see this being all that difficult, so I'll probably think about it later this week, and hopefully have an solution (an efficient one that is) by Sunday.