A greedy solution makes each choice once and never goes back. It is right only when some argument shows the choice is safe: it leaves at least as much for later, or swapping it into any other answer costs nothing. Eleven moves, fifteen problems.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.
A 20 can be paid with a 10 and a 5 or with three 5s. Both work now, but a 5 is also change for a 10 and a 10 is not, so the 10 goes first and the drawer keeps the bill that pays for more.
lemonadeChange([5, 5, 10, 10, 20])?
After the two 10s the drawer holds two 10s and no 5. The 20 is owed 15, and no mix of 10s makes 15.
Why is a 20 paid with a 10 and a 5 rather than three 5s?
A 10 is only ever change for a 20, but a 5 pays for a 10 as well. Spending the 10 keeps the more useful bill.
Customers pay 5, 10 or 20 for a 5 lemonade, in a fixed order, and the drawer starts empty. Can everyone get change?
A 10 is owed one 5. A 20 is owed 15, as a 10 and a 5 or as three 5s. A 5 can be change for a 10 or a 20, but a 10 only for a 20, so the 10 is the bill to spend first. Twenties are never change at all, so only the 5s and 10s are counted.
bool lemonadeChange(vector<int>& bills) { int five = 0, ten = 0; for (int b : bills) { if (b == 5) five++; // no change owed else if (b == 10) { if (five == 0) return false; five--; ten++; } else { // a 20: 15 is owed if (ten > 0 && five > 0) { ten--; five--; } // spend the 10 first else if (five >= 3) five -= 3; else return false; } } return true; }
public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; for (int b : bills) { if (b == 5) five++; // no change owed else if (b == 10) { if (five == 0) return false; five--; ten++; } else { // a 20: 15 is owed if (ten > 0 && five > 0) { ten--; five--; } // spend the 10 first else if (five >= 3) five -= 3; else return false; } } return true; }
def lemonadeChange(bills): five = ten = 0 for b in bills: if b == 5: five += 1 # no change owed elif b == 10: if five == 0: return False five -= 1 ten += 1 else: # a 20: 15 is owed if ten > 0 and five > 0: # spend the 10 first ten -= 1 five -= 1 elif five >= 3: five -= 3 else: return False return True
Three 5s before a 10 and a 5. Both pay a 20 now, but spending three 5s can leave no 5 for the next 10. On 5, 5, 5, 5, 10, 20, 10 the wrong order fails at the last customer.
Read the trees left to right and remember the last occupied point. Room on the left is no use to any later tree, so take it. Falling right can cost only the next tree, which this one replaces.
canPlaceFlowers([0, 0, 1, 0, 0, 0, 0], 3)?
Plots 0, 4 and 6. Plot 3 sits beside the flower at 2, and planting at 4 still leaves plot 6 free.
In Woodcutters, why is falling left tried before falling right?
Every later tree stands further right, so the space to the left of this one can only ever be used by this one.
Plant n flowers in a bed of 0s and 1s so that no two flowers are adjacent. Is there room?
Read the bed left to right and plant in every empty plot whose neighbours are empty. Planting at the first legal plot never hurts. Any plan that plants later in the same run can move that flower left to here, and the plot after it is then free for the next.
bool canPlaceFlowers(vector<int>& flowerbed, int n) { int m = flowerbed.size(); for (int i = 0; i < m && n > 0; i++) { if (flowerbed[i] == 1) continue; bool left = i == 0 || flowerbed[i - 1] == 0; bool right = i == m - 1 || flowerbed[i + 1] == 0; if (left && right) { flowerbed[i] = 1; n--; } // the first legal plot } return n <= 0; }
public boolean canPlaceFlowers(int[] flowerbed, int n) { int m = flowerbed.length; for (int i = 0; i < m && n > 0; i++) { if (flowerbed[i] == 1) continue; boolean left = i == 0 || flowerbed[i - 1] == 0; boolean right = i == m - 1 || flowerbed[i + 1] == 0; if (left && right) { flowerbed[i] = 1; n--; } // the first legal plot } return n <= 0; }
def canPlaceFlowers(flowerbed, n): m = len(flowerbed) for i in range(m): if n <= 0: break if flowerbed[i] == 1: continue left = i == 0 or flowerbed[i - 1] == 0 right = i == m - 1 or flowerbed[i + 1] == 0 if left and right: flowerbed[i] = 1 # the first legal plot n -= 1 return n <= 0
Forgetting to mark the plot. Without flowerbed[i] = 1, the next plot still sees an empty left neighbour, and [0, 0, 0] seems to hold three flowers instead of two.
Trees stand at increasing points along a road. Each may fall left or right by its height, or stand, and no fallen tree may cover an occupied point. Fell as many as you can.
Go left to right and remember prev, the last point taken. Fall left whenever x − h > prev: that space is behind every tree still to come, so it costs them nothing. Otherwise fall right if x + h stays short of the next tree. That can block only the next tree, and this one counts in its place, so it is never worse than standing.
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<long long> x(n), h(n); for (int i = 0; i < n; i++) scanf("%lld %lld", &x[i], &h[i]); long long prev = LLONG_MIN; // the last occupied point int cnt = 0; for (int i = 0; i < n; i++) { if (x[i] - h[i] > prev) { cnt++; prev = x[i]; } // fell it left else if (i == n - 1 || x[i] + h[i] < x[i + 1]) { cnt++; prev = x[i] + h[i]; } // right else prev = x[i]; // it stands } printf("%d\n", cnt); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; long[] x = new long[n], h = new long[n]; for (int i = 0; i < n; i++) { in.nextToken(); x[i] = (long) in.nval; in.nextToken(); h[i] = (long) in.nval; } long prev = Long.MIN_VALUE; // the last occupied point int cnt = 0; for (int i = 0; i < n; i++) { if (x[i] - h[i] > prev) { cnt++; prev = x[i]; } // fell it left else if (i == n - 1 || x[i] + h[i] < x[i + 1]) { cnt++; prev = x[i] + h[i]; } // right else prev = x[i]; // it stands } System.out.println(cnt); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) x = list(map(int, data[1:2 * n + 1:2])) h = list(map(int, data[2:2 * n + 2:2])) prev, cnt = float("-inf"), 0 # the last occupied point for i in range(n): if x[i] - h[i] > prev: # room on the left: fell it left cnt += 1 prev = x[i] elif i == n - 1 or x[i] + h[i] < x[i + 1]: # room on the right cnt += 1 prev = x[i] + h[i] else: # it stands prev = x[i] print(cnt) main()
A segment that only touches the next tree. The segments are closed, so x + h equal to the next x covers that tree's point. The test is x + h < x[i + 1], and on the left x − h > prev, both strict.
Woodcutters with trees (x, h) = (1, 2), (2, 1), (5, 10), (10, 9), (19, 1)?
The first falls left to [−1, 1] and the second right to [2, 3]. The trees at 5 and 10 fit neither way, and the last falls right. With the last tree at 20 instead, 10 could fall right to [10, 19]: the second sample's 4.
A jump may stop short, so every index up to reach can be reached. Raise reach to i + nums[i] at each index. If i ever passes reach, nothing lands on i.
The indices first reached with k jumps form one block. end marks where the current block stops and far where the next one will. Reaching end costs one jump and moves end to far.
canJump([3, 2, 1, 0, 4])?
Indices 0 to 3 all reach exactly 3: 0 + 3, 1 + 2, 2 + 1 and 3 + 0. Index 4 is never reached.
Why does jump stop reading at index n − 2?
If the last index closed a level, the loop would add a jump away from the goal. [0] would need 1 jump instead of 0.
From index i you may jump up to nums[i] steps forward. Can you reach the last index from the first?
Every index up to reach can be reached, because a jump may stop short. So one number, the furthest index reached so far, says everything. Read left to right and raise it to i + nums[i]. If i ever passes reach, nothing before i lands on it, and nothing after it can be reached either.
bool canJump(vector<int>& nums) { int reach = 0; // the furthest index reachable for (int i = 0; i < (int)nums.size(); i++) { if (i > reach) return false; // stranded before i reach = max(reach, i + nums[i]); } return true; }
public boolean canJump(int[] nums) { int reach = 0; // the furthest index reachable for (int i = 0; i < nums.length; i++) { if (i > reach) return false; // stranded before i reach = Math.max(reach, i + nums[i]); } return true; }
def canJump(nums): reach = 0 # the furthest index reachable for i, v in enumerate(nums): if i > reach: return False # stranded before i reach = max(reach, i + v) return True
Overwriting reach instead of taking the max. reach = i + nums[i] forgets a longer jump made earlier. On [3, 0, 0, 1] it shrinks reach to 1 at index 1 and answers false.
The same jumps, and the last index is always reachable. What is the fewest number of jumps?
Split the indices into levels: level k is every index that first becomes reachable with k jumps. It is breadth-first search, but each level is a contiguous block, so two numbers describe it. end is the last index of the current level, and far is the furthest any index in it jumps. When i reaches end, the level is done, one more jump is spent, and the next level ends at far.
int jump(vector<int>& nums) { int jumps = 0, end = 0, far = 0; // end: the last index of this level for (int i = 0; i + 1 < (int)nums.size(); i++) { far = max(far, i + nums[i]); // the next level reaches far if (i == end) { // this level is used up jumps++; end = far; } } return jumps; }
public int jump(int[] nums) { int jumps = 0, end = 0, far = 0; // end: the last index of this level for (int i = 0; i + 1 < nums.length; i++) { far = Math.max(far, i + nums[i]); // the next level reaches far if (i == end) { // this level is used up jumps++; end = far; } } return jumps; }
def jump(nums): jumps = end = far = 0 # end: the last index of this level for i in range(len(nums) - 1): far = max(far, i + nums[i]) # the next level reaches far if i == end: # this level is used up jumps += 1 end = far return jumps
Reading the last index too. If the loop runs to n − 1 and the last index happens to close a level, it counts a jump away from the goal. [0] would take 1 jump instead of 0. Stop at n − 2.
jump([2, 3, 1, 1, 4])?
Level 1 is indices 1 and 2. Index 1 jumps as far as 4, the last index, so it is in level 2.
Drive from start and keep the tank. If it goes negative before i + 1, every start from start to i fails too, since each would arrive with less. Try i + 1, and trust the total at the end.
canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])?
g = −2, −2, −2, 3, 3. The tank goes negative at 0, 1 and 2, so start moves to 3. The total is 0, so start 3 works.
The tank goes negative at i. Why skip every start between start and i?
Starting at start, the car reached each of them with a tank of 0 or more. Starting there instead means arriving with 0, which is no better, and it still fails at i.
Stations on a circle: fill gas[i] at station i and burn cost[i] to reach the next. From which station can you go once round? The answer, if any, is unique.
If the total gas is at least the total cost, some start works; otherwise none does. To find it, drive from start and keep the tank. If the tank goes negative before i + 1, no start from start to i works. Each of them would arrive at i with no more gas than this run did. So the next start to try is i + 1, and one pass finds it.
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int total = 0, tank = 0, start = 0; for (int i = 0; i < (int)gas.size(); i++) { int g = gas[i] - cost[i]; total += g; // the whole loop's balance tank += g; // the balance since start if (tank < 0) { // start..i cannot reach i + 1 start = i + 1; tank = 0; } } return total >= 0 ? start : -1; }
public int canCompleteCircuit(int[] gas, int[] cost) { int total = 0, tank = 0, start = 0; for (int i = 0; i < gas.length; i++) { int g = gas[i] - cost[i]; total += g; // the whole loop's balance tank += g; // the balance since start if (tank < 0) { // start..i cannot reach i + 1 start = i + 1; tank = 0; } } return total >= 0 ? start : -1; }
def canCompleteCircuit(gas, cost): total = tank = start = 0 for i in range(len(gas)): g = gas[i] - cost[i] total += g # the whole loop's balance tank += g # the balance since start if tank < 0: # start..i cannot reach i + 1 start = i + 1 tank = 0 return start if total >= 0 else -1
Restarting at i instead of i + 1. Station i is the one the car could not leave with enough gas, so starting there fails too. The next candidate is i + 1.
Record each letter's last index. Reading left to right, the part must stretch to the last copy of every letter in it. When i reaches that end, cut, as early as the rule allows.
partitionLabels("ababcbacadefegdehijhklij")?
The last a is at 8, so the first part is 0 to 8. Then the last e at 15 closes the second part, and the last j at 23 the third.
Why does cutting as early as possible give the most parts?
Any valid cut can move left to the first point where nothing comes back. Waiting longer only glues together pieces that were free to separate.
Cut a string into as many parts as possible so that each letter appears in one part only. Return the part sizes.
A part that holds a letter must reach that letter's last copy. So record each letter's last index first. Then read left to right, stretching end to the last index of every letter seen. When i reaches end, nothing inside the part appears later, and cutting there as early as possible leaves the most room for more parts.
vector<int> partitionLabels(string s) { int last[26] = {}; for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i; vector<int> out; int start = 0, end = 0; for (int i = 0; i < (int)s.size(); i++) { end = max(end, last[s[i] - 'a']); // this part must reach here if (i == end) { // nothing in it comes back out.push_back(end - start + 1); start = i + 1; } } return out; }
public List<Integer> partitionLabels(String s) { int[] last = new int[26]; for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i; List<Integer> out = new ArrayList<>(); int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { end = Math.max(end, last[s.charAt(i) - 'a']); // this part must reach here if (i == end) { // nothing in it comes back out.add(end - start + 1); start = i + 1; } } return out; }
def partitionLabels(s): last = {c: i for i, c in enumerate(s)} # the last index of each letter out, start, end = [], 0, 0 for i, c in enumerate(s): end = max(end, last[c]) # this part must reach here if i == end: # nothing in it comes back out.append(end - start + 1) start = i + 1 return out
end = last[c] without the max. A letter whose last copy is near can pull end back inside a part that must reach further. On "abab" the second a pulls end back from 3 to 2, so "aba" is cut off and the two b's land in different parts.
Each * could be three things, but the open counts it allows always form a range. Keep its ends, lo and hi. hi below 0 fails every reading; lo below 0 is clipped, since that reading has broken.
checkValidString("(*))")?
Read * as (: (()) balances. lo and hi both end at 0.
checkValidString(")(*")?
The first ) has no ( before it in any reading, so hi drops to −1 at once.
Why is lo raised back to 0 when it goes negative?
A reading with more ) than ( so far can never recover. Dropping it leaves the readings still alive, whose fewest open count is 0.
A string of (, ) and *, where each * may be (, ) or nothing. Can it be a balanced string?
With no stars, one count of open brackets decides it. With stars, the count could be several numbers at once, but always a whole range of them. So keep lo and hi, the fewest and the most open brackets possible. ( raises both, ) lowers both, and * lowers lo and raises hi. If hi drops below 0, every reading has a ) too many. A reading below 0 has already broken, so lo is raised back to 0. At the end, 0 must be in the range.
bool checkValidString(string s) { int lo = 0, hi = 0; // the fewest and most '(' open for (char c : s) { if (c == '(') { lo++; hi++; } else if (c == ')') { lo--; hi--; } else { lo--; hi++; } // '*': ')', '(' or nothing if (hi < 0) return false; // too many ')' in every reading lo = max(lo, 0); // a reading below 0 has broken } return lo == 0; }
public boolean checkValidString(String s) { int lo = 0, hi = 0; // the fewest and most '(' open for (char c : s.toCharArray()) { if (c == '(') { lo++; hi++; } else if (c == ')') { lo--; hi--; } else { lo--; hi++; } // '*': ')', '(' or nothing if (hi < 0) return false; // too many ')' in every reading lo = Math.max(lo, 0); // a reading below 0 has broken } return lo == 0; }
def checkValidString(s): lo = hi = 0 # the fewest and most '(' open for c in s: if c == '(': lo += 1 hi += 1 elif c == ')': lo -= 1 hi -= 1 else: # '*': ')', '(' or nothing lo -= 1 hi += 1 if hi < 0: return False # too many ')' in every reading lo = max(lo, 0) # a reading below 0 has broken return lo == 0
Letting lo go negative. A negative lo stands for a reading with more ) than (, which can never recover. Without the clamp, "(*)" ends with lo = −1 and is rejected, though reading * as nothing balances it.
Each child has a rule for the left neighbour and one for the right. Meet the left rules going right, then the right rules going left, keeping the larger need. Each count is the least allowed.
candy([1, 0, 2])?
[2, 1, 2]: both ends beat the 0 in the middle, which keeps 1.
candy([1, 2, 2])?
[1, 2, 1]: the second 2 equals its left neighbour rather than beating it, so 1 is enough.
Why does the second pass take a max?
The count must satisfy both neighbours. Overwriting it with the right pass's need can drop below what the left neighbour requires.
Children in a row, each with a rating. Everyone gets at least one candy, and a child rated higher than a neighbour gets more than that neighbour. The fewest candies in all?
Each child has two rules, one per neighbour, and they can be met separately. A left-to-right pass gives each child one more than its left neighbour when it is rated higher. A right-to-left pass does the same against the right neighbour, keeping the larger of the two needs. Every count is the least its rules allow, so the sum is the fewest.
int candy(vector<int>& ratings) { int n = ratings.size(); vector<int> c(n, 1); // everyone gets one for (int i = 1; i < n; i++) // beat the left neighbour if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1; for (int i = n - 2; i >= 0; i--) // beat the right one too if (ratings[i] > ratings[i + 1]) c[i] = max(c[i], c[i + 1] + 1); return accumulate(c.begin(), c.end(), 0); }
public int candy(int[] ratings) { int n = ratings.length; int[] c = new int[n]; Arrays.fill(c, 1); // everyone gets one for (int i = 1; i < n; i++) // beat the left neighbour if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1; for (int i = n - 2; i >= 0; i--) // beat the right one too if (ratings[i] > ratings[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1); int sum = 0; for (int x : c) sum += x; return sum; }
def candy(ratings): n = len(ratings) c = [1] * n # everyone gets one for i in range(1, n): # beat the left neighbour if ratings[i] > ratings[i - 1]: c[i] = c[i - 1] + 1 for i in range(n - 2, -1, -1): # beat the right one too if ratings[i] > ratings[i + 1]: c[i] = max(c[i], c[i + 1] + 1) return sum(c)
Dropping the max in the second pass. c[i] = c[i + 1] + 1 can lower a count the left pass needed. On [1, 2, 3, 1] it gives the 3 two candies, no more than the 2 beside it.
The answer is built as a stack. A larger letter on top steps aside for a smaller one only if a later copy can replace it. A letter that never comes back stays put.
removeDuplicateLetters("bcabc")?
a pops c and then b, since both appear again later. b and c are then pushed after it.
When may the top of the stack be popped?
Larger alone is not enough: a letter that never comes back would be lost from the answer.
Remove duplicate letters so that each letter appears once, keeping the order of the rest, and return the result that is smallest in dictionary order.
Build the answer as a stack. Before pushing c, a larger letter on top may be popped if it appears again later, since that later copy can stand in for it after c. A letter with no later copy must stay, and a letter already on the stack is skipped. It is the monotonic stack, with one extra test.
string removeDuplicateLetters(string s) { int last[128] = {}; bool in[128] = {}; // is it on the stack? for (int i = 0; i < (int)s.size(); i++) last[s[i]] = i; string st; // the answer, as a stack for (int i = 0; i < (int)s.size(); i++) { char c = s[i]; if (in[c]) continue; // already placed while (!st.empty() && st.back() > c && last[st.back()] > i) { in[st.back()] = false; // it comes back later: let it wait st.pop_back(); } st.push_back(c); in[c] = true; } return st; }
public String removeDuplicateLetters(String s) { int[] last = new int[128]; boolean[] in = new boolean[128]; // is it on the stack? for (int i = 0; i < s.length(); i++) last[s.charAt(i)] = i; StringBuilder st = new StringBuilder(); // the answer, as a stack for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (in[c]) continue; // already placed while (st.length() > 0 && st.charAt(st.length() - 1) > c && last[st.charAt(st.length() - 1)] > i) { in[st.charAt(st.length() - 1)] = false; // it comes back later st.deleteCharAt(st.length() - 1); } st.append(c); in[c] = true; } return st.toString(); }
def removeDuplicateLetters(s): last = {c: i for i, c in enumerate(s)} st, placed = [], set() # the answer as a stack; what is on it for i, c in enumerate(s): if c in placed: continue # already placed while st and st[-1] > c and last[st[-1]] > i: placed.discard(st.pop()) # it comes back later: let it wait st.append(c) placed.add(c) return "".join(st)
Popping a letter that never comes back. Without the last[top] > i test the stack is a plain monotonic stack, and on "cbacdcbc" the d is popped for the b and lost. The answer would be "abc", with no d at all.
The deadlines add up to the same in any order, so only the finishing times matter. A task's duration delays itself and every task after it, so the shortest runs first.
Tasks and Deadlines with (a, d) = (6, 10), (8, 15), (5, 12)?
Shortest first: 5 ends at 5 (+7), 6 at 11 (−1), 8 at 19 (−4). 7 − 1 − 4 = 2.
In Tasks and Deadlines, why do the deadlines not affect the best order?
The total is the sum of deadlines minus the sum of finishing times, and only the second sum depends on the order.
Run all n tasks one after another; a task with deadline d finishing at f earns d − f, which may be negative. The largest total?
The total is (sum of deadlines) − (sum of finishing times), and the first sum does not depend on the order. A task's duration is paid in its own finishing time and in every later one. Swap two neighbours so the shorter runs first and the later finish stays put while the earlier one moves up. So run the shortest first.
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<long long> a(n); long long total = 0; for (int i = 0; i < n; i++) { long long d; scanf("%lld %lld", &a[i], &d); total += d; } sort(a.begin(), a.end()); // the shortest first long long now = 0; for (int i = 0; i < n; i++) { now += a[i]; total -= now; } // it finishes at now printf("%lld\n", total); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; long[] a = new long[n]; long total = 0; for (int i = 0; i < n; i++) { in.nextToken(); a[i] = (long) in.nval; in.nextToken(); total += (long) in.nval; // every deadline counts once } Arrays.sort(a); // the shortest first long now = 0; for (int i = 0; i < n; i++) { now += a[i]; total -= now; } // it finishes at now System.out.println(total); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) a = sorted(map(int, data[1:2 * n + 1:2])) # durations, the shortest first total = sum(map(int, data[2:2 * n + 2:2])) # every deadline counts once, in any order now = 0 for d in a: now += d # this task finishes at now total -= now print(total) main()
Sorting by deadline. It feels like scheduling, but no task can be skipped, so the deadlines only add a constant. On (4, 9), (2, 4), (1, 7), (3, 6) the deadline order earns 3 and the shortest-first order earns 6. The sum of finishing times passes 2³¹ too, so keep it in 64 bits.
Jobs each take one unit of time and pay a profit only if finished by their deadline. Return how many jobs a most profitable schedule does, and its profit.
A set of jobs fits if, sorted by deadline, the kth job's deadline is at least k. So take jobs in deadline order and keep the profits taken in a min-heap. When the heap holds more jobs than the current deadline allows, the least profitable one is dropped: the one whose loss costs least. It is Heaps' take-it-back move with deadlines as the budget.
vector<int> jobSequencing(vector<int> &deadline, vector<int> &profit) { int n = deadline.size(); vector<pair<int, int> > jobs(n); for (int i = 0; i < n; i++) jobs[i] = make_pair(deadline[i], profit[i]); sort(jobs.begin(), jobs.end()); // by deadline priority_queue<int, vector<int>, greater<int> > kept; // the smallest on top int total = 0; for (int i = 0; i < n; i++) { kept.push(jobs[i].second); total += jobs[i].second; if ((int)kept.size() > jobs[i].first) { total -= kept.top(); kept.pop(); } } return {(int)kept.size(), total}; }
public ArrayList<Integer> jobSequencing(int[] deadline, int[] profit) { int n = deadline.length; Integer[] idx = new Integer[n]; for (int i = 0; i < n; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> deadline[a] - deadline[b]); // by deadline PriorityQueue<Integer> kept = new PriorityQueue<>(); // the smallest on top int total = 0; for (int i : idx) { kept.add(profit[i]); total += profit[i]; if (kept.size() > deadline[i]) total -= kept.poll(); // drop the least profitable } return new ArrayList<>(Arrays.asList(kept.size(), total)); }
import heapq def jobSequencing(deadline, profit): jobs = sorted(zip(deadline, profit)) # by deadline kept = [] # profits taken, the smallest on top for d, p in jobs: heapq.heappush(kept, p) if len(kept) > d: # more jobs than slots up to d heapq.heappop(kept) # drop the least profitable return [len(kept), sum(kept)]
Taking the most profitable jobs first and never looking back. Sorted by profit, a job must go in the latest free slot up to its deadline, not the earliest. Putting it in the earliest blocks a job with a tighter deadline. The heap version avoids slots altogether.
jobSequencing([4, 1, 1, 1], [20, 10, 40, 30])?
Three jobs share deadline 1 and only one fits, so the heap keeps the 40. The job with deadline 4 adds 20.
Moving the target one unit costs 1 for each stick on one side and saves 1 on the other. At the median the two sides are equal, so no move helps.
Stick Lengths on [2, 3, 1, 5, 2]?
Sorted, 1, 2, 2, 3, 5: the median is 2, and the gaps are 1 + 0 + 0 + 1 + 3.
Why the median and not the mean?
Past the median, more sticks lie behind the target than ahead of it, so every further unit adds more cost than it removes.
Make every stick the same length; changing a length by x costs x. The least total cost?
Picture the target t sliding along the sorted lengths. Raising it by 1 costs 1 for every stick at or below it and saves 1 for every stick above. While fewer sticks are below than above, moving up pays. The two sides balance at the middle stick, so the median is the target, not the mean.
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<long long> p(n); for (int i = 0; i < n; i++) scanf("%lld", &p[i]); sort(p.begin(), p.end()); long long m = p[n / 2], cost = 0; // a median for (int i = 0; i < n; i++) cost += llabs(p[i] - m); printf("%lld\n", cost); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; long[] p = new long[n]; for (int i = 0; i < n; i++) { in.nextToken(); p[i] = (long) in.nval; } Arrays.sort(p); long m = p[n / 2], cost = 0; // a median for (int i = 0; i < n; i++) cost += Math.abs(p[i] - m); System.out.println(cost); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) p = sorted(map(int, data[1:n + 1])) m = p[n // 2] # a median print(sum(abs(x - m) for x in p)) main()
The mean instead of the median. The mean minimises the sum of squared gaps, not of gaps. On 1, 2, 2, 2, 3, 9, 12 the mean, about 4.4, costs 23 and the median 2 costs 19. The cost can also pass 2³¹.
Sort the coins. If every sum to reach can be made, a coin up to reach + 1 extends that run by its own value. A larger coin leaves reach + 1 out for good.
Missing Coin Sum on [1, 1, 3, 7]?
1, 1 and 3 cover 1 to 5. The next coin, 7, is larger than 6, so 6 can never be made.
Why is reach + 1 the best number to patch in?
Any number up to reach + 1 extends the run, and a larger one extends it further. reach + 1 is the largest that leaves no gap.
Given coins, find the smallest sum that no subset of them adds up to.
Sort the coins and keep reach: every sum from 1 to reach can be made with the coins read so far. A next coin c ≤ reach + 1 extends that run, since each old sum plus c covers reach + 1 to reach + c. A coin c > reach + 1 leaves reach + 1 unmakeable for good, because every coin left is at least c.
#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); vector<long long> x(n); for (int i = 0; i < n; i++) scanf("%lld", &x[i]); sort(x.begin(), x.end()); long long reach = 0; // every sum 1..reach can be made for (int i = 0; i < n; i++) { if (x[i] > reach + 1) break; // reach + 1 can never be made reach += x[i]; } printf("%lld\n", reach + 1); }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; long[] x = new long[n]; for (int i = 0; i < n; i++) { in.nextToken(); x[i] = (long) in.nval; } Arrays.sort(x); long reach = 0; // every sum 1..reach can be made for (int i = 0; i < n; i++) { if (x[i] > reach + 1) break; // reach + 1 can never be made reach += x[i]; } System.out.println(reach + 1); } }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) reach = 0 # every sum 1..reach can be made for c in sorted(map(int, data[1:n + 1])): if c > reach + 1: break # reach + 1 can never be made reach += c print(reach + 1) main()
Reading the coins unsorted. A large coin read early stops the scan before the small coins that would have closed the gap. Unsorted, [2, 1] answers 1 instead of 4. reach also passes 2³¹, so keep it in 64 bits.
A sorted array and a number n. Add the fewest numbers so that every value from 1 to n is the sum of some subset.
Row 14's argument, used to build. With every sum up to reach covered, a next number at most reach + 1 extends the run for free. When the next number is too big, or there is none, reach + 1 must be added, and reach + 1 is the best number to add: it is the largest that still joins the run, so reach jumps to 2 · reach + 1.
int minPatches(vector<int>& nums, int n) { long long reach = 0; // every sum 1..reach can be made int i = 0, patches = 0; while (reach < n) { if (i < (int)nums.size() && nums[i] <= reach + 1) reach += nums[i++]; else { reach += reach + 1; patches++; } // add reach + 1, the best patch } return patches; }
public int minPatches(int[] nums, int n) { long reach = 0; // every sum 1..reach can be made int i = 0, patches = 0; while (reach < n) { if (i < nums.length && nums[i] <= reach + 1) reach += nums[i++]; else { reach += reach + 1; patches++; } // add reach + 1, the best patch } return patches; }
def minPatches(nums, n): reach, i, patches = 0, 0, 0 # every sum 1..reach can be made while reach < n: if i < len(nums) and nums[i] <= reach + 1: reach += nums[i] # the next number extends the run i += 1 else: reach += reach + 1 # add reach + 1, the best patch patches += 1 return patches
reach in 32 bits. n can be 2³¹ − 1, and reach can pass it on the last step, so reach < n overflows and loops for ever. Keep reach in 64 bits.
minPatches([1, 3], 6)?
1 covers 1. 3 is larger than 2, so patch in 2: reach is 3. Then 3 extends reach to 6.
Eleven moves, and each has a phrase in the statement that gives it away.
take the one that leaves the more useful resources
KEEP THE OPTIONSO(n)go left to right and take the leftmost legal spot
LEAVE ROOMO(n)carry the furthest index, or levels of it
REACHO(n)a negative running balance moves the start past it
DRY TANKO(n)stretch to each letter's last index, then cut
LAST OCCURRENCEO(n)keep the range of possible counts, not every reading
RANGE OF COUNTSO(n)one pass per side, the larger need wins
TWO PASSESO(n)a stack where a letter that comes back may wait
STACK THAT WAITSO(n)sort by the key that swapping two neighbours proves
EXCHANGE ARGUMENTO(n log n)meet at the median
MEDIANO(n log n)sorted, every sum up to reach is covered
UP TO REACHO(n log n)Assign cookies to children so the most are content; a child needs a cookie at least their greed. Which move?
Sort both, then give each child the smallest cookie that satisfies them. Swapping a larger cookie to a less greedy child never helps. It is Assign Cookies (dp-2).
Minimum Number of Taps to Open to Water a Garden: each tap waters [i − r, i + r]. Which move?
For each left end keep the furthest right end any tap starting there covers. Then it is Jump Game II: levels of reach, one tap per level.
Arrange numbers to form the largest number when written side by side. Which move?
Put a before b when a + b beats b + a as strings. Swapping two neighbours that break that rule makes the number larger. It is Largest Number (sorting).
What does a greedy solution need before it can be trusted?
Taking the best-looking option is often wrong. A greedy solution is right only when some argument shows the choice loses nothing: it stays ahead, or a swap into any other answer costs nothing.
None of these fail the samples. Each one fails a hidden test.
Greedy fails silently. Before coding, find the argument: the choice leaves at least as much for later, or swapping it into any other answer costs nothing. Without one, test it on a brute force.
Tasks and Deadlines sorts by duration, not deadline, and Stick Lengths meets at the median, not the mean. The key comes from the swap argument, not from what the statement mentions first.
Woodcutters' segments are closed, so a tree may not end on the next tree's point. Strict and non-strict comparisons decide many greedy problems.
When the tank goes dry at i, starting at i fails too. The next start to try is i + 1.
Candy's right-to-left pass must keep the larger of the two needs. Overwriting the count loses what the left neighbour required.
Finishing times, stick costs, coin reach and Patching Array's reach all pass 2³¹ on large inputs. Keep them in 64-bit integers.
Eleven moves on one page. The right column is the cue for each.
The 10 was spent and the 5 kept; trees fell left while the left was free; reach and levels of reach replaced every path; a dry tank moved the start past it; a part stretched to each letter's last copy; two numbers held every reading of the stars; one pass per neighbour paid the candies; a letter that comes back waited; the shortest task ran first; the sticks met at the median; and every sum up to reach was covered. Assign Cookies (dp-2) and Largest Number (sorting) are unit 9's swap argument, and the interval greedies sort by end in Intervals and Sweep.
Module 21. Fifteen problems: ten on LeetCode, three on CSES, one on Codeforces and one on GeeksforGeeks. Next in the sheet: intervals and sweep.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.