Once upon a time, this was a 'solved problem in computer science', and the solution strength-reduced to O(n log n), somewhat down from NP-complete. Glibc has bits of it in Linux, Solaris depended on it, and it was first thoroughly discussed on Multics. I'll try to do the archeology and write it up in my Copious Spare Time.