At the same time we had to keep performance in mind and not try to find the most optimal solution, just something good enough.

Yeah, lol it's an NP hard problem. I'm not surprised.