search

walkccc / CLRS

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

Update 16.1.md #369

Closed mrscooter closed 3 years ago

mrscooter commented 3 years ago

O(n . log n) algorithm for the exercise 16.1-5 is described and proved correct. Original solution was in cubic time. Please write me if you have anything to fix in my proposal. I can make it even more formal if-need-to-be. I tried to keep it not too much formal, readable also for a non-mathematician.

walkccc commented 3 years ago

Nice, this is actually a greedy way to solve the problem in O(nlogn). Thank you :)