search

walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition
https://walkccc.me/CLRS
MIT License
4.65k stars 1.26k forks source link

wrong solution to 16.1-5 #396

Open gand opened 3 years ago

gand commented 3 years ago

Hi, First of all thanks for this project, it's very useful!

Now, I believe the proposed O(nlgn) solution to 16.1-5 (https://walkccc.me/CLRS/Chap16/16.1/) is wrong. Let's consider three activities: a1={s=1, f=3, v=2}, a2={s=2, f=5, v=4}, a3={s=3, f=6, v=3}. The proposed solution will:

  1. add a1 // this is just the start
  2. remove a1 and add a2. // they overlap and a2.v > a1.v
  3. will not add a3 // a2 and a3 overlap, a2.v > a3.v It will give a result with total value = 4. But the correct solution should be <a1, a3>, total value = 5. Regards, Andrzej