Codility MaxNonoverlappingSegments Java solution

Рет қаралды 1,604

2 жыл бұрын

MaxNonoverlappingSegments in the first exercise in the Greedy algorithms lesson on Codility. The aim is to find the maximum number of segments that don't overlap in a set of segments defined in two given arrays.
The segments are pre-sorted by end position. I keep track of the current position, which is the end of each segment that I consider, I then scan over the arrays to find lines that start after the current position and count the segments when I find a line that doesn't overlap.
This solution scores 100% on Codility.

Пікірлер: 9

@bootagain 2 жыл бұрын

Thanks for your valuable video!

@javadave 2 жыл бұрын

Glad it was helpful!

@WhiteSiroi Жыл бұрын

Great vid and explanation, helped me a lot, thank you DK

@javadave Жыл бұрын

Thanks WS!

@huynhviet5154 2 жыл бұрын

How long does it take you to think about the silution?

@javadave 2 жыл бұрын

Some I can do straight away and others take a bit of time. I think for me, about 2 hours is the maximum. I've been coding for years.

@NivagSwerdna 2 жыл бұрын

I think you got lucky there... doesn't this only work when the first segment is in the largest set? Inevitably the loop with pick up A[0] since that is going to have A[0]>-1

@NivagSwerdna 2 жыл бұрын

I'm thinking that B[K] ≤ B[K + 1] guarantees your solution but having a hard time wrapping my head around it!

@javadave 2 жыл бұрын

@@NivagSwerdna Hi. Its a while since I did this, but having a quick look at it now, I think it works because the lines are sorted by end position. The first one is definitely going to end before any subsequent ones, so when we're looking for another one that starts after it, the first one we find will always do. I think the problem would be a lot harder if they weren't sorted like this.