Checking is cheaper than building

The gap between verifying an answer and producing one is the whole reason consultants exist.

Every NP problem shares a defining shape: somebody hands you a candidate answer, and you can check it in a reasonable amount of time. Verifying that a delivery route hits every stop, that a schedule violates no rules, that a circuit design wires up correctly — all fast. Producing the route, the schedule, the design in the first place can be vastly harder. The asymmetry between checking and producing is where most of the difficulty in software engineering hides. Build pipelines are checkers. Test suites are checkers. Code review is a checker. The hard, slow, expensive work — the actual writing, planning, designing — is on the producing side. When your team can describe a checker for a problem but cannot describe a producer, the problem is probably NP. Treat the estimate accordingly.

A schedule checker is a tight loop over the constraints — one pass, no search. Producing a valid schedule from the same constraints is the expensive half and would call a solver. Same data, two complexity classes.

struct Shift { staff: u32, start: u32, end: u32 }

fn schedule_is_valid(shifts: &[Shift], min_gap: u32) -> bool {
    let mut by_staff: std::collections::HashMap<u32, Vec<&Shift>> = Default::default();
    for s in shifts { by_staff.entry(s.staff).or_default().push(s); }
    for assignments in by_staff.values_mut() {
        assignments.sort_by_key(|s| s.start);
        for w in assignments.windows(2) {
            if w[0].end + min_gap > w[1].start { return false; }
        }
    }
    true
}

HashMap<K, V> is Rust's hash table — a keyed lookup that takes a key and gives you back a value in roughly constant time. Vec<T> is a growable list of T stored in one contiguous block. Combined here as HashMap<u32, Vec<&Shift>>, the map keys are staff IDs and each value is the list of that person's shifts. The reason for the grouping: the no-overlap rule only applies within one person's day — Alice's morning shift cannot conflict with Bob's afternoon. Group first, then we only have to worry about one person at a time.

// What the grouped data looks like after the first loop:
//
//   by_staff:
//     17  ─►  [Shift { start:  900, end: 1300, .. },
//             Shift { start: 1400, end: 1800, .. }]
//     42  ─►  [Shift { start: 1000, end: 1400, .. }]
//     91  ─►  [Shift { start:  800, end: 1200, .. },
//             Shift { start: 1230, end: 1700, .. }]
//
// .entry(key) is the canonical "get or insert" pattern.
// .or_default() inserts an empty Vec the first time we see a staff ID.
// .push(s) appends — Vec grows automatically.
let mut by_staff: HashMap<u32, Vec<&Shift>> = HashMap::new();
for s in shifts {
    by_staff.entry(s.staff).or_default().push(s);
}

03

Sort each person's shifts by start time, then walk consecutive pairs. windows(2) is a slice helper that yields every overlapping pair: [a, b], then [b, c], then [c, d]. After sorting, if shift w[0] ends at minute 1300 and shift w[1] starts at minute 1310, the actual gap is 10 minutes. The rule "at least min_gap between shifts" means w[1].start − w[0].end ≥ min_gap, which rearranges to w[0].end + min_gap ≤ w[1].start. If the left side is greater, the gap was violated and the schedule is invalid.
```
// Sort puts the earliest start first; windows(2) walks adjacent pairs.
assignments.sort_by_key(|s| s.start);
for w in assignments.windows(2) {
    // Want: w[1].start  -  w[0].end  >=  min_gap
    // i.e.: w[0].end + min_gap  <=  w[1].start
    // Violation is the opposite:
    if w[0].end + min_gap > w[1].start {
        return false;
    }
}
// If no pair fails for any staff member, the schedule is valid.
```

One staff member's timeline. The earlier shift ends, then a buffer, then the next shift starts. When the buffer is at least min_gap, the schedule is fine; when it is less, the check fails on this pair and the function short-circuits with false.

min_gap = 30 minutes

OK  (gap = 60 min, passes)
    ─────────────────────────────────────────────────────────────►  time
              w[0]                              w[1]
       ╔══════════════╗      gap = 60 min      ╔══════════════╗
       ║  09:00 –     ║◄─────────────────────► ║  14:00 –     ║
       ║       13:00  ║                        ║       18:00  ║
       ╚══════════════╝                        ╚══════════════╝
                       ↑                       ↑
                       w[0].end = 13:00        w[1].start = 14:00
                       13:00 + 30 = 13:30  ≤  14:00   ✓


FAIL  (gap = 10 min, fails)
    ─────────────────────────────────────────────────────────────►  time
              w[0]                w[1]
       ╔══════════════╗  10 min ╔══════════════╗
       ║  09:00 –     ║◄──────► ║  13:10 –     ║
       ║       13:00  ║         ║       17:10  ║
       ╚══════════════╝         ╚══════════════╝
                       ↑        ↑
                       13:00 + 30 = 13:30  >  13:10   ✗  return false

In plain terms

Think about a math contest. One person solves the problems. Another person grades the solutions. Both jobs have to finish before the bell rings. Grading is much, much easier than solving — that is why grading happens in minutes and solving takes the whole contest period. Almost every interesting problem in computing has the same shape. Checking that an answer is correct is one job. Finding the answer in the first place is a different and usually much harder job.

This matters for estimating because the two jobs are easy to confuse. A product manager looking at a problem like "schedule our drivers to cover every shift with no conflicts" might assume that, since the rules are simple to check, the planning must be simple to do. It is not. The rules-checker is a polynomial-time algorithm that fits on one screen. The planner is an NP-complete optimization that needs an industrial solver.

The reverse error is equally common. A team facing a problem where checking would actually require running an expensive simulation might assume the producer is correspondingly expensive. Often it is not. Sometimes the producer is a one-line library call and the team has been overengineering.

The skill is reading a problem and asking two questions in sequence: Could I write a checker that runs fast on a finished answer? If yes, the problem is at most NP — possibly easier. Then: Do I know of a fast producer? If yes, the problem is in P and is a known job. If no, prepare for a search.

Checking is cheap. Building is the expensive half. Estimate the half you are actually doing.