Course contentsShow
← Computer Science
Lesson 900 of 2,87221. Greedy AlgorithmsFree lesson

Policemen Catch Thieves Problem

Maximize thieves caught by greedily pairing each policeman with the nearest uncaught thief within range.

Policemen Catch Thieves Problem

What you'll learn: How to maximize the number of thieves caught by pairing each policeman with the nearest uncaught thief within their allowed range using a greedy strategy.


The Problem Setup

Imagine a street represented as a line where policemen and thieves are positioned at various points. Each policeman can only catch thieves within a certain distance k from their position. Your goal: catch as many thieves as possible.

The Greedy Approach

The key insight is to use a greedy strategy: for each policeman (or thief), pair them with the nearest available match within range. This works because:

  1. Sorting first by position gives us a natural left-to-right order
  2. Pairing nearby ensures we don't "waste" a policeman on a distant thief when a closer one exists
  3. Making locally optimal choices (nearest pairing) leads to the globally optimal solution

Think of it like organizing carpools: you wouldn't send a driver from the north end of town to pick up someone from the south end if there's an uncaught passenger nearby.

Why It Works

This problem has the greedy choice property and optimal substructure. Once you pair a policeman with the nearest thief, you can solve the remaining subproblem independently. By always choosing the closest valid pair, you ensure no policeman is "blocked" by skipping over a nearby thief for a farther one.

The algorithm typically involves:

  • Marking positions as policeman (P) or thief (T)
  • Iterating through positions
  • For each P, searching within range [position - k, position + k] for the nearest unmatched T
  • Marking successful matches

Key Takeaway: The Policemen Catch Thieves problem demonstrates greedy pairing by distance—always match with the nearest valid option to maximize total catches without wasting resources.