parikshan

Intervals

The core idea

An interval is [start, end]. Almost every interval problem is solved by sort by start, then sweep. The sweep maintains a running "in-progress" set; you process events in order and update the set as intervals open and close.

Two patterns cover most questions:

  1. Overlap detection / merge: sort by start; if the next interval's start is ≤ the current's end, merge; otherwise commit the current and move on.
  2. Resource counting: split each interval into two events (start +1, end -1), sort the events, sweep, and track the running sum. The max of the running sum is the peak concurrent count.

When to reach for it

Trigger phrases:

  • "meetings", "schedules", "time slots"
  • "merge overlapping ..."
  • "find a free slot / busy slot"
  • "minimum rooms / agents / cars to handle these reservations"
  • "first interval that conflicts with ..."

How to approach

  1. Decide whether you care about overlap (merge) or count (events).
  2. Sort. Pick the right key. Always confirm: by start? by end? does the tie-breaker matter?
  3. Sweep. Maintain the running invariant.
  4. Edge cases: a single interval; intervals that touch at endpoints (does "touching" count as overlap?); zero-length intervals.

Enterprise scenarios

  • Google Calendar, Microsoft Outlook: free/busy time and conflict detection.
  • AWS Lambda concurrent execution limits: counting overlapping invocations against a quota.
  • Uber surge pricing: peak concurrent ride requests per geofence per minute.
  • Hotel and airline reservations: room and seat conflict detection at scale.
  • Cloudflare / Fastly rate limiting: counting overlapping rate-bucket lifetimes.
  • PagerDuty oncall scheduling: detecting handoff overlaps and gaps.
  • Stripe billing: prorating overlapping subscription windows.
  • Compliance log analysis: detecting overlapping audit-relevant events in financial systems.

In the AI-integrated workspace

AI agents tend to write interval code with the wrong sort key. The most common error: sort by length, or by end time when start time was the right key (or vice versa). Always demand a one-line justification of the sort.

The second common error: using < where <= was right (or vice versa) for the touch-vs-overlap distinction. The spec must say whether [1,5] and [5,10] conflict. Generated code rarely raises that ambiguity; you have to.

In an integrated learning loop, this is a place to be ruthless during code review. Sketch the timeline on paper, run two adjacent intervals through the code mentally, and verify the boundary case before you trust the suite.

Problems in this cluster

Easy: meeting-rooms. Medium: merge-intervals.

Start with meeting-rooms. The "do these overlap" question is the smallest possible building block, and it is the basis for every other interval problem.