SyntaxPilot
Courses/DSA and Coding Problems/Lesson 60
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 60 of 90

Gas station and task scheduler

queued

These are the notes for DSA episode 60: two interview classics where a short proof turns a slow search into one pass. Part 1, Gas Station: a delivery van on a ring road of petrol pumps; where should it start? Trying every start is correct but O(n²): about 15 seconds for 1,00,000 pumps (Time Limit Exceeded on LeetCode). Two facts (the total decides whether any start works, and if the tank runs dry at pump i, no pump from the start to i can be the start) give an O(n) answer. Part 2, Task Scheduler: a CPU with a cooldown between runs of the same task. Trying every order is correct but Time Limit Exceeded on 20 tasks; a greedy "first ready task, alphabetically" gives 4 where 3 is possible; the frame built by the most frequent task gives a formula. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.

The problem, in real life

Part 1. A delivery van must drive once around a ring road (like a city's Outer Ring Road). At pump i it can fill gas[i] litres; driving from pump i to the next burns cost[i] litres. The tank starts empty. Where should it start so it gets all the way round? If nowhere works, answer -1.

Part 2. In cricket a bowler can't bowl two overs in a row. A CPU has a similar rule: each time unit it runs one task or sits idle, and two runs of the same task type need at least n units between them (a cooldown). What's the fewest time units to finish all tasks?

Real life In code
Pump i's fuel / the stretch to the next pump gas[i] / cost[i]
Net fuel at pump i d = gas[i] - cost[i]
Tank level while driving running sum of d from the start
A bowler / an over / rest rule a task letter / one time unit / cooldown n

Every word, from zero

  • Circular route (ring): after the last pump comes pump 0 again; (s + k) % n wraps around.
  • Net gain gas[i] - cost[i]: what the tank gains (or loses) from pump i to the next.
  • Total: Σ (gas[i] - cost[i]) over all pumps.
  • Prefix sum / running sum: the tank after each stretch, starting from some pump (episode 5).
  • Cooldown n: at least n time units between two runs of the same task.
  • Idle: a time unit where the CPU runs nothing.
  • Frequency / count: how many times a task letter appears.
  • max, numMax: the largest count, and how many letters have it.
  • Greedy: best-looking choice now, never undone (episode 59); it needs a proof.
  • Bottleneck: the part that limits the whole schedule; here, the most frequent task.

Part 1: Gas Station (LeetCode 134)

Problem

gas cost Answer
[1, 2, 3, 4, 5] [3, 4, 5, 1, 2] 3
[2, 3, 4] [3, 4, 3] -1

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ gas[i], cost[i] ≤ 10^4. If a solution exists, it is unique.

Example 1 from pump 3: fill 4, burn 1 → 3; fill 5 → 8, burn 2 → 6; fill 1 → 7, burn 3 → 4; fill 2 → 6, burn 4 → 2; fill 3 → 5, burn 5 → 0. Back at pump 3 with 0 litres: it works.

Obvious idea: try every start

import java.util.*;

public class Main {
    static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int s = 0; s < n; s++) {
            int tank = 0, k = 0;
            for (; k < n; k++) {
                int i = (s + k) % n;
                tank += gas[i] - cost[i];
                if (tank < 0) break;
            }
            if (k == n) return s;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
        System.out.println(canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
    }
}
3
-1

Correct. Now 1,00,000 pumps where every start fails near the end of the ring except the last pump (gas = cost = 1 everywhere, except cost[n - 2] = 2 and gas[n - 1] = 2):

start 99999, 14713 ms

About 15 seconds (it varies by machine); LeetCode allows about one second: Time Limit Exceeded. n starts × up to n stretches = O(n²) ≈ 500 crore steps.

The key insight: two facts

  1. Fact 1: if total = Σ (gas - cost) < 0, no start works (the van burns more than all the fuel on the ring): -1. If total ≥ 0, some start works (a classic result; the second fact finds it).
  2. Fact 2: start at s, and say the tank first goes negative at pump i. Then no pump between s and i can be the start: we reached each of them with a tank of zero or more, so starting there with an empty tank is no better, and we'd still run dry by i. So jump the start to i + 1 with an empty tank.
  3. The start still standing after one pass is the answer (when total ≥ 0).

By hand on example 1 (d = [-2, -2, -2, +3, +3]):

i d tank start
0 -2 -2 → reset 0 1
1 -2 -2 → reset 0 2
2 -2 -2 → reset 0 3
3 +3 3 3
4 +3 6 3

total = 0 ≥ 0: answer 3.

Solution in Java

import java.util.*;

public class Main {
    static int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int d = gas[i] - cost[i];
            total += d;
            tank += d;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total < 0 ? -1 : start;
    }
    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 1, 2}));
        System.out.println(canCompleteCircuit(new int[]{2, 3, 4}, new int[]{3, 4, 3}));
        System.out.println(canCompleteCircuit(new int[]{5}, new int[]{4}));
        System.out.println(canCompleteCircuit(new int[]{3, 1}, new int[]{1, 3}));
    }
}
3
-1
0
0

The 1,00,000 pumps: start 99999, 4 ms.

The same Gas Station solution in C++

#include <bits/stdc++.h>
using namespace std;

// Gas Station (LeetCode 134): one pass; restart after any pump where the tank goes negative.
int canCompleteCircuit(const vector<int>& gas, const vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        int d = gas[i] - cost[i];
        total += d;
        tank += d;
        if (tank < 0) { start = i + 1; tank = 0; }
    }
    return total < 0 ? -1 : start;
}

int main() {
    cout << canCompleteCircuit({1, 2, 3, 4, 5}, {3, 4, 5, 1, 2}) << "\n";
    cout << canCompleteCircuit({2, 3, 4}, {3, 4, 3}) << "\n";
    cout << canCompleteCircuit({5}, {4}) << "\n";
    cout << canCompleteCircuit({3, 1}, {1, 3}) << "\n";
}
3
-1
0
0

The same Gas Station solution in Python

# Gas Station (LeetCode 134): total decides; restart at i + 1 with an empty tank when it goes negative.
def can_complete_circuit(gas, cost):
    total = tank = start = 0
    for i, (g, c) in enumerate(zip(gas, cost)):
        total += g - c
        tank += g - c
        if tank < 0:
            start, tank = i + 1, 0
    return -1 if total < 0 else start

print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
print(can_complete_circuit([2, 3, 4], [3, 4, 3]))
print(can_complete_circuit([5], [4]))
print(can_complete_circuit([3, 1], [1, 3]))
3
-1
0
0

Part 2: Task Scheduler (LeetCode 621)

Problem

tasks are letters A-Z, run in any order, one per time unit (or idle). Two runs of the same letter need at least n units between them. Return the fewest units.

tasks n Answer A schedule
AAABBB 2 8 A B idle A B idle A B
AAABBB 0 6 A A A B B B
AAAAAABCDEFG 2 16 A B C A D E A F G A idle idle A idle idle A

Constraints: 1 ≤ tasks.length ≤ 10^4, 0 ≤ n ≤ 100.

Obvious idea: try every order

best tries every letter as the next task, waits until it's ready, and recurses; ready[c] is when letter c may run again.

import java.util.*;

public class Main {
    static int leastInterval(char[] tasks, int n) {
        int[] count = new int[26], ready = new int[26];
        for (char t : tasks) count[t - 'A']++;
        return best(count, ready, 0, tasks.length, n);
    }
    static int best(int[] count, int[] ready, int time, int left, int n) {
        if (left == 0) return time;
        int res = Integer.MAX_VALUE;
        for (int c = 0; c < 26; c++) {
            if (count[c] == 0) continue;
            int start = Math.max(time, ready[c]), old = ready[c];
            count[c]--;
            ready[c] = start + n + 1;
            res = Math.min(res, best(count, ready, start + 1, left - 1, n));
            count[c]++;
            ready[c] = old;
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(leastInterval("AAABBB".toCharArray(), 2));
        System.out.println(leastInterval("AAABBB".toCharArray(), 0));
        System.out.println(leastInterval("AAAAAABCDEFG".toCharArray(), 2));
    }
}
8
6
16

On 20 tasks (AABBCC…JJ, ten letters twice each): Time Limit Exceeded: 20! / 2^10 ≈ 2,400 trillion orders.

A greedy trap: the first ready letter

Every unit, run the first ready letter in alphabetical order; idle if none is ready:

import java.util.*;

public class Main {
    static int leastInterval(char[] tasks, int n) {
        int[] count = new int[26], ready = new int[26];
        for (char t : tasks) count[t - 'A']++;
        int time = 0, left = tasks.length;
        while (left > 0) {
            for (int c = 0; c < 26; c++)
                if (count[c] > 0 && ready[c] <= time) {
                    count[c]--;
                    ready[c] = time + n + 1;
                    left--;
                    break;
                }
            time++;
        }
        return time;
    }
    public static void main(String[] args) {
        System.out.println(leastInterval("AAABBB".toCharArray(), 2));
        System.out.println(leastInterval("AAABBB".toCharArray(), 0));
        System.out.println(leastInterval("AAAAAABCDEFG".toCharArray(), 2));
        System.out.println(leastInterval("ACC".toCharArray(), 1));
    }
}
8
6
16
4

The examples pass, but ACC with n = 1 gives 4 (A C idle C); C A C takes 3. The rule ignores the bottleneck: the letter with the most copies left should go first (that rule, with a max-heap, is correct; see the mini project).

The key insight: the frame of the most frequent task

Let max = the largest count and numMax = how many letters have it.

  • The max copies of the bottleneck letter need n slots after each of the first max - 1 copies: max - 1 blocks of n + 1 slots, then a last row.
  • The last row holds every letter tied for max: numMax slots.
  • frame = (max - 1) × (n + 1) + numMax. Other letters fill the gaps; leftover gaps are idle.
  • If there are more tasks than gaps, widen the blocks: the cooldown still holds and there's no idle at all, so the answer is just tasks.length.
  • Answer = max(tasks.length, frame).

AAABBB, n = 2:

A B idle | A B idle | A B      (3 - 1) × 3 + 2 = 8

Solution in Java

import java.util.*;

public class Main {
    static int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks) count[t - 'A']++;
        int max = 0, numMax = 0;
        for (int c : count) {
            if (c > max) { max = c; numMax = 1; }
            else if (c == max) numMax++;
        }
        return Math.max(tasks.length, (max - 1) * (n + 1) + numMax);
    }
    public static void main(String[] args) {
        System.out.println(leastInterval("AAABBB".toCharArray(), 2));
        System.out.println(leastInterval("AAABBB".toCharArray(), 0));
        System.out.println(leastInterval("AAAAAABCDEFG".toCharArray(), 2));
        System.out.println(leastInterval("ACC".toCharArray(), 1));
        System.out.println(leastInterval("A".toCharArray(), 100));
    }
}
8
6
16
3
1

The 20 tasks that timed out: 20 units, 0 ms; 10,000 random tasks with n = 100: 41613 units, 0 ms.

The same Task Scheduler solution in C++

#include <bits/stdc++.h>
using namespace std;

// Task Scheduler (LeetCode 621): answer = max(len, (max - 1) * (n + 1) + numMax).
int leastInterval(const string& tasks, int n) {
    int count[26] = {0};
    for (char t : tasks) count[t - 'A']++;
    int mx = *max_element(count, count + 26);
    int numMax = count_if(count, count + 26, [&](int c) { return c == mx; });
    return max((int)tasks.size(), (mx - 1) * (n + 1) + numMax);
}

int main() {
    cout << leastInterval("AAABBB", 2) << "\n";
    cout << leastInterval("AAABBB", 0) << "\n";
    cout << leastInterval("AAAAAABCDEFG", 2) << "\n";
    cout << leastInterval("ACC", 1) << "\n";
    cout << leastInterval("A", 100) << "\n";
}
8
6
16
3
1

The same Task Scheduler solution in Python

from collections import Counter

# Task Scheduler (LeetCode 621): the most frequent task builds the frame.
def least_interval(tasks, n):
    counts = Counter(tasks).values()
    mx = max(counts)
    num_max = sum(1 for c in counts if c == mx)
    return max(len(tasks), (mx - 1) * (n + 1) + num_max)

print(least_interval("AAABBB", 2))
print(least_interval("AAABBB", 0))
print(least_interval("AAAAAABCDEFG", 2))
print(least_interval("ACC", 1))
print(least_interval("A", 100))
8
6
16
3
1

Three real bugs

Bug 1: no total check (Gas Station)

return start;:

3
2

Example 2 should be -1: the last start standing only works if there's enough fuel in total.

Bug 2: moving the start but not emptying the tank

Without tank = 0;:

4
-1

Example 1 gives 4 instead of 3: the new start carried the old debt (-6).

Bug 3: the frame without max (Task Scheduler)

return (max - 1) * (n + 1) + numMax;:

8
4
16

AAABBB with n = 0 gives 4, but there are 6 tasks: you can't finish 6 tasks in 4 units.

Complexity

Approach Time Space Big input
Gas: every start O(n²) O(1) 1 lakh pumps: ~15 s
Gas: one pass O(n) O(1) 4 ms
Tasks: every order exponential O(26) + recursion 20 tasks: Time Limit Exceeded
Tasks: first ready letter O(answer · 26) O(26) wrong (4 instead of 3)
Tasks: max-heap simulation O(answer · log 26) O(26) correct, prints the order
Tasks: frame formula O(n) O(26) instant

Common mistakes

Mistake What you see (real) Why Fix
No total check 2 instead of -1 not enough fuel overall total < 0 ? -1 : start
Start moved, tank kept 4 instead of 3 carried the old debt tank = 0
Restart at i instead of i + 1 wrong start pump i itself made the tank negative start = i + 1
First ready letter (alphabetical) 4 instead of 3 ignores the bottleneck most frequent first, or the frame
Frame only 4 instead of 6 more tasks than slots max(tasks.length, frame)
Counting only one letter at max 7 instead of 8 ties fill the last row numMax

Mini project: print an actual schedule

A max-heap of counts: every unit, run the ready letter with the most copies left (the bottleneck first); letters cooling down wait in a queue.

import java.util.*;

public class Main {
    // Mini project: Task Scheduler simulation with a max-heap (most remaining first) and a cooldown queue.
    static String schedule(String tasks, int n) {
        int[] count = new int[26];
        for (char t : tasks.toCharArray()) count[t - 'A']++;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] != b[1] ? b[1] - a[1] : a[0] - b[0]);
        for (int c = 0; c < 26; c++) if (count[c] > 0) heap.add(new int[]{c, count[c]});
        Deque<int[]> cooling = new ArrayDeque<>();   // {letter, left, ready time}
        StringBuilder out = new StringBuilder();
        for (int time = 0; !heap.isEmpty() || !cooling.isEmpty(); time++) {
            if (!cooling.isEmpty() && cooling.peek()[2] == time) {
                int[] c = cooling.poll();
                heap.add(new int[]{c[0], c[1]});
            }
            if (heap.isEmpty()) { out.append("_ "); continue; }
            int[] t = heap.poll();
            out.append((char) ('A' + t[0])).append(' ');
            if (t[1] > 1) cooling.add(new int[]{t[0], t[1] - 1, time + n + 1});
        }
        return out.toString().trim();
    }
    public static void main(String[] args) {
        System.out.println(schedule("AAABBB", 2));
        System.out.println(schedule("ACC", 1));
        System.out.println(schedule("AAAABBC", 2));
    }
}
A B _ A B _ A B
C A C
A B C A B _ A _ _ A

(_ is an idle unit; the lengths 8, 3 and 10 match the formula.)

Practice

1. Reorganize String (LeetCode 767). Rearrange a string so no two adjacent letters are equal, or return "".

Solution

Task Scheduler with n = 1 and no idles allowed: possible exactly when max ≤ (len + 1) / 2. Place the most frequent letter at even indices first, then the rest.

from collections import Counter

# Reorganize String (LeetCode 767): fill even indices, then odd, most frequent letter first.
def reorganize_string(s):
    counts = Counter(s)
    if max(counts.values()) > (len(s) + 1) // 2:
        return ""
    res, i = [""] * len(s), 0
    for ch, c in sorted(counts.items(), key=lambda x: -x[1]):
        for _ in range(c):
            res[i] = ch
            i += 2
            if i >= len(s):
                i = 1
    return "".join(res)

print(reorganize_string("aab"))
print(reorganize_string("aaab"))
print(reorganize_string("aaabbc"))
aba

ababac

(The middle line is the empty string: aaab can't be rearranged.)

2. Gas Station, but return the tank level at every pump for the answer's start. Hint: run the one-pass algorithm, then simulate once from start.

3. Candy (LeetCode 135). Children in a line with ratings; each gets at least one candy, and a child with a higher rating than a neighbour gets more than that neighbour. Fewest candies? Hint: two greedy passes, left-to-right then right-to-left, taking the max.

Solution
import java.util.*;

public class Main {
    // Candy (LeetCode 135): left pass for the left neighbour, right pass for the right neighbour.
    static int candy(int[] r) {
        int n = r.length;
        int[] c = new int[n];
        Arrays.fill(c, 1);
        for (int i = 1; i < n; i++) if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--) if (r[i] > r[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
        int sum = 0;
        for (int x : c) sum += x;
        return sum;
    }
    public static void main(String[] args) {
        System.out.println(candy(new int[]{1, 0, 2}));
        System.out.println(candy(new int[]{1, 2, 2}));
        System.out.println(candy(new int[]{1, 3, 4, 5, 2}));
    }
}
5
4
11

Quick quiz

tasks = "AAAABBC", n = 2. What does leastInterval return? A) 10 B) 7 C) 9 D) 12

Answer

A) 10. max = 4 (A), numMax = 1: (4 - 1) × 3 + 1 = 10, bigger than the 7 tasks. A schedule: A B C A B _ A _ _ A.

Interview questions

  1. Why does total ≥ 0 guarantee a start exists? Start right after the point where the running sum of d is lowest; from there, every prefix sum is ≥ 0. The one-pass algorithm finds exactly that point.
  2. Why can we skip pumps s..i after failing at i? Each was reached with a non-negative tank; starting there empty can only be worse, and it would still fail by i.
  3. Gas Station complexity? O(n) time, O(1) space.
  4. Explain the task-scheduler formula. The most frequent letter forces max - 1 blocks of n + 1 slots plus a last row of the tied letters; if other tasks overflow the gaps, there's no idle and the answer is the task count.
  5. When is the answer exactly tasks.length? When (max - 1)(n + 1) + numMax ≤ tasks.length: enough variety to fill every gap.
  6. How would you print the schedule? Simulate with a max-heap of remaining counts and a queue of cooling letters.
  7. Why is "first ready letter" wrong? It may spend the slots on a rare letter and leave the frequent one to cool down with nothing else to run.

Glossary

Term Meaning
Circular route After the last pump comes the first
Net gain gas[i] - cost[i]
Total The sum of all net gains
Running sum (tank) Net gains added from the start pump
Cooldown n Minimum gap between two runs of the same task
Idle A time unit with no task
Frequency, max, numMax A letter's count; the largest count; letters with that count
Frame (max - 1) × (n + 1) + numMax slots
Bottleneck The part that limits the whole schedule
Max-heap Gives the largest item first (episode 43)

Summary

  • Gas Station: total < 0 → -1; otherwise, whenever the tank goes negative at i, restart at i + 1 with an empty tank. One pass, O(n).
  • Task Scheduler: the most frequent task builds the frame; answer = max(tasks.length, (max - 1)(n + 1) + numMax), O(n).
  • Trying every start is O(n²); trying every order is exponential; "first ready letter" is a greedy trap.
  • Watch for: no total check, no tank reset, and forgetting the max with the task count.
  • Next episode: Huffman coding and minimum cost to connect ropes: greedy with a heap.