Is the following problem decidable in polynomial time?
This is a nice exercise, such as one might find in an undergrad-level algorithms class.  (Congratulate your professor on selecting such a nice exercise.)  Since it's your exercise, I'm going to let you solve it, but I'll give you a series of hints.

Important: Spend at least an hour exploring each hint, before moving on to the next hint.



Hint #1:


  When given an algorithms problem, it is often very helpful to look at some small examples and work out what's going on by hand.
  
  So, pick a sample problem instance with 3 items (generate the $x_i,y_i$'s arbitrarily); map out all possible timelines (all possible sequences of item removals); and see what you see.  Do another example with 3 items.  Try one with 4 items.  Do a few such examples, and see if you can build some intuition.  I suspect you'll spot what is going on, and then from that you might be able to figure out how to solve the problem.




Hint #2:


   What chapter of the textbook are you currently in?  This is often a good heuristic to help you select a type of algorithm to try.




Hint #3:


   A natural algorithmic approach is to use a greedy algorithm: if multiple items are currently eligible for removal, select the item whose $y_i$ value is _____.  (You fill in the blank.)  So, see if you can determine whether you can find any way to fill in the blank that provides a correct algorithm for your problem.  This gives you a few candidate algorithms; for each candidate, see if you can prove or disprove its correctness.  To do that, try some small examples.  See if you can find a proof of correctness or a counterexample demonstrating it is incorrect.  Once you've worked out whether there is any algorithm of this form that is correct, you should be able to answer your question.




Hint #4:


   If you've tried all of the above diligently, show us your work and where you got stuck and I'll give you one more hint.