Open and Close Interval Trick

Introduction

In some DP problems, we need to build groups (or intervals) where the final value depends on the first and last element of each group. A very useful pattern for this is the Open and Close Interval Trick.

The idea is simple:

We process elements in sorted order.
We allow groups to be temporarily open.
Later we close them when their right end is fixed.

This lets us avoid explicitly tracking all interval endpoints.

Problem Statement

We are given $n$ coders with skill levels from $0$ to $100$ . We want to divide them into teams so that the total penalty is at most $x$ .

For a team, penalty = difference between highest and lowest skill.

Total penalty = sum of penalties of all teams.

Count the number of valid ways to form teams.

Key Idea

Sort coders by skill.
Now every team becomes a contiguous segment in sorted order.

While scanning coders from left to right:

some teams are already finished
some teams are still open (we chose the minimum, but not yet the maximum)

So DP tracks how many teams are currently open.

DP State

Let

Open and Close Interval Trick

Introduction

Problem Statement

Key Idea

DP State

Cost Update Trick

Transitions

1) Single-person team

2) Add to an open team (keep open)

3) Close an open team

4) Start a new open team

Final Answer

Implementation