So there are two boxing teams, my team A and the opposing team B, each with m boxers. Based on the player's ranking of skill, x_subscript(i) being the ranking for ith boxer for team A and y_subscript(k) being the ranking for kth box for team B. Each fight round is set up one boxer from team A against one boxer from team B at a time. I get to set up who goes against whom, so I need to make sure the boxer from my team A has a higher ranking than the boxer from team B for as many rounds as possible.

I need to provide a greedy algorithm and prove that it's correct, and come up with the running time.

It seems to me it's a type permutation, scheduling with deadlines and apply the inversion, but I am stuck on how to start. Could someone provide a guidace? Thank you!

  • $\begingroup$ What have you tried? What greedy strategies have you considered? We want to help you understand, not solve your exercises for you. If you don't tell us what you've tried, where you got stuck, how much you understand about greedy algorithms, what studying you have done, etc., it is very hard to help you. $\endgroup$ – D.W. Oct 20 '14 at 1:20
  • $\begingroup$ @D.W. Certainly. I too would like to learn... I tried a few that were given, but permutation was the correct way to go but I just don't know how to apply to this case because there was a problem similar that I only practiced with where they were from the same interval, for example, x_subscript(i) and y_subscript(i), and not different with i and k for this. So I just want a starting guidance. $\endgroup$ – O M Oct 20 '14 at 1:26
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Oct 20 '14 at 5:07

Usually it is easy to identify a few candidate greedy strategies. Once you've got some candidates, try them on some test cases. Try to build a test case (a counterexample) that "kills" each candidate greedy strategy. If you find a test case where a candidate strategy does not give the optimal solution, you can cross that off your list. If you've done a good job at identifying candidates and looking for counterexamples, typically you'll be able to cross off all candidates except for one. Now you have a candidate greedy algorithm -- all you need to do from this point forward is see if you can prove it correct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.