Lemonade Change Problem

A lemonade stand sells each cup for $5. Customers pay with either a $5, $10, or $20 bill, and you must provide exact change for each transaction, starting with no cash on hand. Determine whether you can serve all customers successful.

The approach becomes straightforward once we identify three scenarios:

1. Customer pays $5: accept the bill directly.
2. Customer pays $10: give back one $5 as change.
3. Customer pays $20: prefer to return one $10 and one $5; if that fails, try returning three $5 bills.

The key greedy insight lies in the third scenario. Since a $10 bill can only serve as change for a $20 payment, whereas a $5 bill can cover change for both $10 and $20 payments, we should always attempt to use the $10 bill first when handling a $20 transaction. This local heuristic—conserving the more versatile $5 bills—directly supports the global goal of completing all transactions without running out of change.

bool canGiveChange(vector<int>& payments) {
    int count5 = 0, count10 = 0;
    for (int p : payments) {
        if (p == 5) {
            count5++;
        } else if (p == 10) {
            if (count5 == 0) return false;
            count5--;
            count10++;
        } else if (p == 20) {
            if (count5 > 0 && count10 > 0) {
                count5--;
                count10--;
            } else if (count5 >= 3) {
                count5 -= 3;
            } else {
                return false;
            }
        }
    }
    return true;
}

The twenty-dollar bill counter is intentionally omitted since it never serves as change.

Reconstructing a Queue by Height

Given an array where each element [h, k] represents a person of height h with exactly k taller or equal-height people ahead of them, reconstruct the original queue.

We handle two dimensions by first sorting people in descending order of height. If heights match, the one with a smaller k comes first. After sorting, we insert each person into the result list at the position indicated by their k value. Because taller individual are added before shorter ones, later insertions do not invalidate the earlier placements.

Consider people [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]. Sorting yields [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]. Insertions proceed:

• Insert [7,0] → [[7,0]]
• Insert [7,1] → [[7,0],[7,1]]
• Insert [6,1] → [[7,0],[6,1],[7,1]]
• Insert [5,0] → [[5,0],[7,0],[6,1],[7,1]]
• Insert [5,2] → [[5,0],[7,0],[5,2],[6,1],[7,1]]
• Insert [4,4] → [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

A possible implementation:

vector<vector<int>> rebuildQueue(vector<vector<int>>& persons) {
    auto compare = [](const vector<int>& a, const vector<int>& b) {
        return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    };
    sort(persons.begin(), persons.end(), compare);
    
    vector<vector<int>> order;
    for (auto& p : persons) {
        int idx = p[1];
        order.insert(order.begin() + idx, p);
    }
    return order;
}

The greedy property: inserting the tallest remaining person at their k index satisfies the queue constraints locally, and composing these steps produces a globally valid solution.

Minimum Arrows to Burst Balloons

You are given a list of balloons represented by their horizontal diameter intervals [xstart, xend]. A vertical arrow shot at coordinate x bursts any balloon whose interval covers x. Find the minimum arrows needed to burst all balloons.

Intuitively, shooting at overlapping intervals saves arrows. To maximize overlap, we sort intervals by their starting coordinates. Traversing left to right, we maintain the current overlapping interval’s right boundary. As soon as a balloon starts beyond this boundary, we need an additional arrow.

Consider intervals [[10,16],[2,8],[1,6],[7,12]]. After sorting: [[1,6],[2,8],[7,12],[10,16]]. The first two intervals overlap and share a boundary at 6; one arrow at x=6 bursts both. The nextt interval starts at 7, which exceeds 6, so a second arrow is needed. This second arrow can cover [7,12] and [10,16], yielding a total of 2 arrows.

int minArrowShots(vector<vector<int>>& balloons) {
    if (balloons.empty()) return 0;
    sort(balloons.begin(), balloons.end(), 
         [](auto& p, auto& q) { return p[0] < q[0]; });
    
    int shots = 1;
    for (size_t i = 1; i < balloons.size(); ++i) {
        if (balloons[i][0] > balloons[i-1][1]) {
            ++shots;
        } else {
            balloons[i][1] = min(balloons[i-1][1], balloons[i][1]);
        }
    }
    return shots;
}

By shrinking the overlapping region’s right bound to the minimum among overlapping balloons, we ensure future balloons are correctly checked against the tightest shared boundary.