Not able to devise a concrete solution for the given graph query

Question

I was trying to solve the following problem:

You are given a grid of size N×N that has the following specifications:

Each cell in the grid contains either a policeman or a thief.

A policeman can only catch a thief if both of them are in the same row. Each policeman can only catch one thief.

A policeman cannot catch a thief who is more than K units away from the policeman.

Write a program to find the maximum number of thieves that can be caught in the grid.

example:

N=3,K=1

P T P

T T P

T P T

Answer:3

I tried a simple BFS solution but my code if failing in which there are alternative P and T,am not able to handle this case with BFS.

My solution:solution(Its a bit lengthy,so didn't paste it here.)

It would be really helpful and highly appreciating if someone could suggest some algorithm or pseudo code for this problem statement.

PS:This was the question of this test.It was a timed test, couldn't solve it.

Thanks.

Answer 1

Your problem is very similar to interval scheduling, and it seems it can be solved similarly using a greedy approach. Note first that you can solve each row separately. For each row, you scan the row from left to right. Assign each policeman to the leftmost thief that he can capture and isn't already taken (if any). Intuitively, this should work, and you can try proving that it does using the standard proof method of comparing the greedy solution to an optimal one.