🚀 Greedy Algorithms: Interval Scheduling & Overlapping Intervals

Harsh Jaiswal

5 min read

·

Sep 26, 2026

--

Listen

Share

While learning Greedy Algorithms, I came across a pattern that was new for me: Intervals.

At first, intervals looked like a simple 2D array problem, but while solving them, I realized that the main challenge is understanding how to sort intervals and what decision to make after sorting.

I recently solved:

• 🔹 LeetCode 452 — Minimum Number of Arrows to Burst Balloons
• 🔹 LeetCode 57 — Insert Interval

These problems helped me understand two important interval patterns:

1. Interval Scheduling
2. Overlapping Intervals

🧠 1. Interval Scheduling

Interval Scheduling problems usually involve intervals like:

[start, end]

The important question is often:

“Which interval should I choose first so that I can make the best possible decisions for the remaining intervals?”

A very common greedy idea is:

👉 Sort intervals by their ending point

Why?

Because if I choose the interval that ends earliest, I leave maximum possible space for the remaining intervals.

For example:

[1,3]
[2,5]
[4,6]
[6,8]

If I choose:

[1,3]

I finish early and can potentially choose more intervals afterward.

This is the basic idea behind Interval Scheduling.

General Pattern

Sort intervals by end time
        ↓
Choose the interval that finishes earliest
        ↓
Update the boundary
        ↓
Continue greedily

This pattern appears in problems involving:

• Maximum number of non-overlapping intervals
• Minimum resources
• Selecting compatible intervals
• Removing conflicting intervals
• Finding the best boundary

🎈 2. Overlapping Intervals

The second important pattern is handling overlapping intervals.

Two intervals overlap when their ranges intersect.

For example:

[1,5]
   [3,7]

They overlap because:

3 <= 5

A very useful condition is:

start <= currentEnd

which means the new interval overlaps with the current interval.

If:

start > currentEnd

then there is no overlap.

🔥 Problem 1 — LeetCode 452

Minimum Number of Arrows to Burst Balloons

Problem

We are given balloons represented as intervals:

[x_start, x_end]

A balloon exists from x_start to x_end.

An arrow is shot vertically at some x coordinate.

If:

x_start <= x <= x_end

the arrow bursts that balloon.

The goal is:

Find the minimum number of arrows needed to burst all balloons.

Example

[10,16]
[2,8]
[1,6]
[7,12]

We want to burst all balloons with minimum arrows.

First, sort them by their ending point:

[1,6]
[2,8]
[7,12]
[10,16]

Now look at the first balloon:

[1,6]

If we shoot an arrow at:

x = 6

it bursts:

[1,6]
[2,8]

because both contain 6.

Now:

[7,12]

doesn’t contain 6, so we need another arrow.

Shoot at:

x = 12

This also bursts:

[10,16]

So the answer is:

2

💡 The Greedy Idea

The important observation is:

When intervals overlap, shoot at the smallest possible ending point.

Why?

Suppose we have:

[1,6]
[2,8]

Their common region is:

[2,6]

If we shoot at 6, we burst both.

Now suppose we have:

[1,6]
[2,8]
[4,10]

The common region is:

[4,6]

Again, shooting at 6 works for all three.

So we keep track of the current end boundary.

🔑 Algorithm

Step 1

Sort intervals by their end:

sort(points.begin(), points.end(),
     [](vector<int>& a, vector<int>& b) {
         return a[1] < b[1];
     });

Step 2

Start with one arrow.

int arrows = 1;

The first arrow is placed at:

points[0][1]

Step 3

Check every next interval.

If:

points[i][0] > arrowPosition

then the current arrow cannot burst this balloon.

So we need another arrow.

Press enter or click to view image in full size

🧠 Dry Run

Input:

[10,16]
[2,8]
[1,6]
[7,12]

After sorting:

[1,6]
[2,8]
[7,12]
[10,16]

Initially:

arrows = 1
arrowPosition = 6

[2,8]

2 <= 6

Overlap.

Same arrow works.

[7,12]

7 > 6

No overlap.

Need another arrow.

arrows = 2
arrowPosition = 12

[10,16]

10 <= 12

Overlap.

Same arrow works.

Final:

2

🔥 Problem 2 — LeetCode 57

Insert Interval

This problem is slightly different.

Here, we are given:

intervals

which are already:

• sorted by starting point
• non-overlapping

and we have:

newInterval

We need to insert it while maintaining the properties.

Example

intervals =
[1,3]
[6,9]

newInterval =
[2,5]

We need to insert [2,5].

But:

[1,3]
[2,5]

overlap.

So we merge them:

[1,5]

Final answer:

[1,5]
[6,9]

🧠 The Three Parts of Insert Interval

This problem becomes much easier when we divide it into three phases.

Phase 1 — Intervals Completely Before New Interval

Suppose:

[1,2]
[3,5]
        [6,8]

and:

newInterval = [6,8]

If:

intervals[i][1] < newInterval[0]

then the current interval is completely before the new interval.

So simply add it.

result.push_back(intervals[i]);

Phase 2 — Overlapping Intervals

Now we find intervals that overlap with newInterval.

The important condition is:

intervals[i][0] <= newInterval[1]

If this is true, the intervals overlap.

Then merge them:

newInterval[0] =
    min(newInterval[0], intervals[i][0]);

newInterval[1] =
    max(newInterval[1], intervals[i][1]);

Example

Suppose:

newInterval = [2,5]

current = [3,7]

They overlap because:

3 <= 5

Merge:

start = min(2,3) = 2
end = max(5,7) = 7

So:

[2,5] + [3,7]

becomes:

[2,7]

Phase 3 — Intervals Completely After New Interval

Once we find:

current.start > newInterval.end

there is no possibility of further overlap.

So we first insert the merged newInterval:

result.push_back(newInterval);

Then add all remaining intervals.

Press enter or click to view image in full size

🧠 Dry Run

Input:

intervals =
[1,3]
[6,9]

newInterval = [2,5]

Phase 1

Check:

[1,3]

Is:

3 < 2

No.

So we don’t add it.

Phase 2

Check:

[1,3]

Does:

1 <= 5

Yes.

So merge:

[2,5]
[1,3]

becomes:

[1,5]

Next:

[6,9]

Check:

6 <= 5

No.

So overlapping part is finished.

Phase 3

Add:

[1,5]

Then add remaining:

[6,9]

Final:

[1,5]
[6,9]

LC 452

We are trying to minimize arrows.

So we maintain the point where the current arrow is placed.

Sort by end
     ↓
Keep arrow at earliest possible end
     ↓
If next interval starts after arrow
     ↓
Need another arrow

LC 57

We are trying to insert one interval correctly.

So we divide the intervals into:

Before
  ↓
Overlapping
  ↓
After

This makes the problem much easier to reason about.

🧩 My Main Learning From These Problems

The biggest thing I learned was that sorting is not just a preprocessing step.

The sorting order determines the greedy strategy.

For interval problems, I now ask:

1️⃣ What does the interval represent?

[start, end]

2️⃣ What should I sort by?

Possibilities:

start
end

3️⃣ What does overlap mean?

Usually:

start <= currentEnd

4️⃣ What boundary should I maintain?

For example:

currentEnd
arrowPosition
newInterval

5️⃣ What greedy decision gives me the most flexibility?

For scheduling problems, an early ending interval often leaves more room for future intervals.

🚀 My Progress

Another pattern added to my Greedy toolkit:

Greedy
   │
   ├── Sorting-based Greedy
   │
   ├── Interval Scheduling ✅
   │
   ├── Overlapping Intervals ✅
   │
   └── More patterns to explore...

These problems made me realize that 2D arrays and intervals aren’t difficult once the right sorting and boundary logic is clear.

I’m continuing to build my Greedy problem-solving skills pattern by pattern, rather than solving problems randomly.

👋 Connect with Me:
🔎LEETCODE :- https://leetcode.com/u/HARSHJAISWAL2707/

👤LinkedIn :- https://www.linkedin.com/in/mr-harsh-jaiswal-76691a32a/

Written by Mr. Harsh Jaiswal — B.Tech CSE | DSA & Web Development

#IntervalScheduling #OverlappingIntervals #GreedyAlgorithm #DSA #CodingInterview #EnjoyProblems