Sorting as a Solution Strategy - C Plus Plus

1. Which strategy uses sorting to obtain a minimum-cost assignment without examining all $n!$ matchings?
   Answer: Sort both vectors in ascending order and pair elements at corresponding positions in the two sorted vectors. Whenever you see an assignment-cost minimization problem, think about what configuration of pairings keeps individual differences small. The key insight is that absolute differences are minimized when large values are paired with large values and small values with small values — not opposites. To see why, consider a simple case: workers = [1, 5], jobs = [2, 6]. Pairing by sorted order gives $|1-2| + |5-6| = 2$. Pairing opposites gives $|1-6| + |5-2| = 8$. Sorting both vectors and pairing at corresponding positions (C) consistently produces the minimum total cost. This is a classic greedy result provable by an exchange argument: swapping any two pairings in a sorted-aligned assignment never decreases the total cost. Choice A describes pairing the smallest worker with the largest job — the opposite of what minimizes differences. This maximizes spread between paired values, inflating the total cost dramatically. Choice B sorts only the workers but leaves jobs unordered. Without aligning the jobs by magnitude, you might accidentally pair a small worker with a large job or vice versa, producing unnecessarily large differences. Both vectors must be sorted for the strategy to work. Choice D describes a greedy nearest-neighbor approach without sorting. While it sounds intuitive, without sorting first, each "closest pair" search costs $O(n^2)$ per step, giving $O(n^3)$ overall — far worse than the $O(n \log n)$ sort-then-pair approach. It also doesn't guarantee a globally optimal result. As a study tip, remember: sort both, align both. Whenever a pairing problem minimizes differences, the optimal strategy always matches rank to rank.
2. Which strategy most directly uses sorting to simplify the problem while meeting the space requirement?
   Answer: Sort the vector, place pointers at both ends, and advance the left pointer when the sum is too small or retreat the right pointer when it is too large. When you see a problem asking you to find a pair summing to a target, think about what sorting buys you: once elements are ordered, you can reason about whether a sum is too small or too large and move accordingly — a classic two-pointer technique. Sorting the vector and placing one pointer at the leftmost (smallest) element and another at the rightmost (largest) gives you directional control. If the sum of the two pointed-to values is less than $T$, you advance the left pointer to increase the sum. If it exceeds $T$, you retreat the right pointer to decrease it. If they equal $T$, you've found your pair. This runs in $O(n)$ after sorting and uses only the two pointer variables — constant auxiliary space — making A the correct answer. B fails because checking only adjacent pairs misses most combinations. For example, if $T = 10$ and the sorted array is $[1, 4, 6, 9]$, the pair $(1, 9)$ sums correctly but is never adjacent. C is flawed for two reasons: binary search is $O(\log n)$ per element (not wrong in complexity, but the real issue is correctness) — allowing the search to return $a$ itself means a single element could be counted twice, producing false positives when $2a = T$ and only one copy of $a$ exists. D sounds like the two-pointer strategy but contains a critical error: discarding both values whenever the sum is wrong, regardless of direction, throws away potentially valid elements and will miss correct pairs. As a study tip, always verify that a pointer or greedy strategy moves in the correct direction based on the comparison — the logic of which pointer moves and when is exactly what exam questions test.
3. Which ordering turns the selection into a correct greedy scan?
   Answer: Sort by ending time and select each activity whose start is at least the end of the last selected activity. Whenever you see a question about scheduling or optimization, think about greedy algorithms — strategies that make locally optimal choices at each step. The Activity Selection Problem is a classic greedy scenario where the key insight is: finishing early leaves the most room for future activities. The reason B is correct comes down to why ending time is the right sorting key. By sorting activities by ending time and selecting each one whose start time $s \geq e_{last}$ (the end of the last chosen activity), you always commit to the activity that frees up the timeline soonest. This maximizes the opportunities available for subsequent selections, provably yielding the maximum number of compatible activities. Choice A is tempting because "pick the earliest start" sounds intuitive — but an activity that starts early might run very long, blocking several shorter activities that could have fit instead. Starting time tells you nothing about when a slot becomes available again. Choice C, sorting by duration, similarly fails. A short activity might start late, conflicting with many others. Duration alone doesn't capture where on the timeline an activity sits. Counterexamples are easy to construct: a 1-minute activity from time 10–11 blocks a 2-minute activity from 5–7 if selected greedily by duration. Choice D reverses the scan direction without logical justification. Selecting activities whose end precedes a previous start means you're building the schedule backwards in a way that doesn't guarantee maximality. Study tip: For any greedy scheduling problem, ask yourself "what metric minimizes future conflicts?" — that metric is almost always the one to sort by, and for activity selection, it's always the ending time.
4. Which preprocessing and scan correctly turn this into a simple one-pass merging problem?
   Answer: Sort by starting point, then extend the current merged ending point while the next starting point does not exceed it. When tackling interval-merging problems, the key insight is: what ordering makes overlapping intervals adjacent and easy to detect in a single pass? If you sort intervals by their starting point, any interval that could possibly overlap with a "current" merged interval will appear consecutively. Once sorted, you maintain a running merged interval and simply ask: does the next interval's start fall at or before the current merged end? If so, the two overlap (or touch), and you extend the merged end to whichever endpoint is larger. This is exactly what C describes — sort by starting point, then extend the current merged endpoint while the next start doesn't exceed it. One clean left-to-right pass handles everything. A sorts by ending point instead of starting point. This breaks the adjacency guarantee — intervals that share a start but have different ends may no longer be neighbors, causing you to miss merges. B is close but too restrictive. It only merges when the next start equals the current end, missing cases where intervals genuinely overlap (next start is less than the current end). For example, [1,5] and [3,7] would be skipped because 3 ≠ 5. D sorts by length, which tells you nothing useful about positional overlap. Two long intervals could be completely disjoint, while two short ones could overlap completely. Length is irrelevant to whether intervals share a region on the number line. As a strategy, whenever you see "merge overlapping intervals," immediately think: sort by start, sweep left to right, extend greedily. That pattern solves the problem efficiently every time.
5. Which event ordering and scan correctly handles reservations that start and end at the same time?
   Answer: Sort events by time, process ending events before starting events at a tie, and track the maximum running active count. When solving "maximum simultaneous reservations" problems, your key insight must be how half-open intervals $[s, e)$ handle boundary collisions. Because a reservation ending at time $t$ does not overlap one starting at time $t$, your event-processing order at ties determines everything. The correct approach, choice A, processes ending events before starting events whenever two events share the same timestamp. This respects the half-open interval definition: if one reservation ends at $t=5$ and another starts at $t=5$, they are never simultaneously active. By decrementing first, then incrementing, your running count accurately reflects this — the outgoing reservation vacates before the incoming one is counted. Tracking the maximum of this running count after each step gives the correct answer. Choice B flips the tie-breaking rule, processing starts before ends. This incorrectly treats a reservation ending at $t=5$ and one starting at $t=5$ as briefly overlapping, artificially inflating your peak count by 1. This is the most tempting trap because it feels natural to process arrivals first. Choice C introduces sorting by duration, which is entirely irrelevant to determining simultaneous overlap. Duration tells you nothing about when intervals coincide; only actual start/end timestamps matter. Choice D discards event types entirely, making it impossible to know whether a given timestamp represents a start or an end. Alternating increments and decrements on sorted times is arbitrary and produces meaningless results. Study tip: Whenever you see half-open intervals $[s, e)$, immediately ask yourself: "What happens at the boundary?" The answer almost always determines your tie-breaking rule — ends before starts.
6. Which approach best exploits sorting to simplify all of the queries?
   Answer: Sort once, use lower_bound(L) and upper_bound(R) for each query, and subtract the first position from the second. When you need to count elements in a range $[L, R]$ across many queries on a fixed dataset, the key insight is: sort once, then use binary search repeatedly. The C++ STL provides two essential tools — lower_bound, which finds the first element not less than a value, and upper_bound, which finds the first element greater than a value. Understanding their difference is what this question is really testing. The correct approach is D. After sorting once ($O(n \log n)$), each query runs in $O(\log n)$. lower_bound(L) gives an iterator to the first element ≥ $L$, and upper_bound(R) gives an iterator one past the last element ≤ $R$. Subtracting these iterator positions gives exactly the count of elements in $[L, R]$, inclusive on both ends. A reverses the two functions — upper_bound(L) skips elements equal to $L$, which incorrectly excludes valid left-boundary values. This is a subtle but critical swap that produces wrong counts whenever $L$ appears in the data. B describes binary-searching an unsorted vector, which is logically invalid. Binary search requires sorted data; applying it to an unsorted container produces undefined, meaningless results. C re-sorts before every query, which is $O(n \log n)$ per query — the worst of all worlds. It eliminates the entire benefit of sorting and makes the solution far slower than even a brute-force linear scan. A helpful memory rule: lower for the left boundary, upper for the right. lower_bound catches elements equal to $L$; upper_bound steps just past elements equal to $R$. Together, they bracket the inclusive range perfectly.
7. Why does sorting allow the function to avoid examining every pair?
   Answer: After sorting, some pair achieving the minimum difference must be adjacent, so only consecutive differences need to be examined. Whenever you see a question about optimizing a search over pairs, ask yourself: does the structure of the data after transformation reduce the search space? That's exactly what sorting does here. When you sort an array, you arrange elements in non-decreasing order. The key insight is that for any two elements, their absolute difference can only grow as they move farther apart in the sorted sequence. Formally, if the sorted array is $a_1 \leq a_2 \leq \cdots \leq a_n$, then $a_j - a_i \leq a_k - a_i$ whenever $i < j < k$. This guarantees that the minimum absolute difference between any two elements must be achieved by some pair of adjacent elements in the sorted order. You can therefore find the answer in a single linear pass — comparing only $(a_2 - a_1),\ (a_3 - a_2), \ldots$ — rather than examining all $O(n^2)$ pairs. B correctly captures this reasoning. A is wrong because the first and last elements produce the maximum difference, not the minimum — they are the farthest apart numerically, so their difference is the range of the data. C is wrong on two counts: binary search isn't the relevant tool here, and claiming the minimum is "always one" when no duplicate exists is simply false — elements can differ by any amount. D is wrong because the median has no special relationship to the minimum difference. The closest pair can appear anywhere in the sorted array, not exclusively near the median. The study takeaway: sorting converts an $O(n^2)$ pair-comparison problem into an $O(n \log n)$ problem by restricting where the optimal pair can hide — always adjacent after sorting.
8. Which sorted-data strategy is sufficient to answer the question?
   Answer: Sort in ascending order and test each consecutive triple to see whether its two smaller lengths sum to more than its largest. Whenever you see a problem about detecting triangles from a collection of values, anchor yourself to the triangle inequality: three lengths $a \leq b \leq c$ form a nondegenerate triangle if and only if $a + b > c.$ The largest side is the binding constraint — if the two smaller sides can't beat it together, no triangle is possible with that triple. Sorting in ascending order and checking every consecutive triple (option D) is the correct strategy. After sorting, each window of three adjacent elements gives you the locally "tightest" test: the two smaller values versus the immediately following larger one. If any consecutive triple satisfies $a + b > c$, a valid triangle exists. This works because if a non-adjacent triple could form a triangle, a consecutive triple would too — sorting guarantees no better candidates are hidden elsewhere. Option A fails because comparing only the two globally smallest lengths against the globally largest ignores all intermediate combinations. You could easily miss a valid triple buried in the middle of the sorted array. Option B sorts descending and checks only the first three (the three longest sticks), which is actually a sound greedy observation — if any triple works, the three largest are the best candidates — but the question asks about ascending-order strategies, and more importantly, understanding why B might work requires the same consecutive-triple logic applied to the front of a descending sort. It's situationally correct but not the reasoning the question rewards. Option C is a misconception: triangles do not require equal sides; any three lengths satisfying the triangle inequality qualify, including scalene triangles. As a study tip, memorize that after sorting, the hardest constraint to satisfy is always $a + b > c$ for adjacent triples — this pattern appears in many geometry and greedy algorithm problems.
9. Which additional requirement would make this direct sorting strategy insufficient unless extra position information were retained and used?
   Answer: The resulting vector must contain each distinct value in the order in which that value first appeared in the input. When you sort a vector and call std::unique + erase, you get each distinct value exactly once — but sorted in ascending order, not in their original first-appearance order. This question tests whether you recognize when that ordering destruction becomes a problem. The requirement that breaks the strategy is B: preserving first-appearance order. If you must output values in the order they first appeared in the input (e.g., input [3, 1, 2, 1, 3] → output [3, 1, 2]), sorting destroys that information permanently. To fix this, you'd need to track each value's first-seen index — for example, by iterating the original vector, using an unordered_set to detect duplicates, and building a result in encounter order. Simply sorting and calling std::unique cannot recover the original ordering. A is actually the ideal use case for sort + std::unique + erase — it produces exactly one copy of each value in ascending order. This makes A wrong as a "breaking" requirement. C is a red herring. If you only need the count of distinct values, you can still sort and use std::unique — just measure the distance rather than keeping the values. Nothing breaks here. D describes the normal situation std::unique is designed to handle after sorting. Sorting moves identical values to be adjacent first, so std::unique eliminates them regardless of where duplicates originally appeared. Study tip: When a question asks what breaks an algorithm, look for a requirement the algorithm actively destroys — here, original ordering is erased by sorting itself, not recoverable afterward.
10. Which sorting strategy reduces the check to comparing neighboring records?
    Answer: Sort lexicographically by user and then timestamp, then compare consecutive timestamps belonging to the same user. Whenever you see a problem involving "find two events per entity within a time threshold," think about what ordering makes the answer fall out naturally. You need two things simultaneously: events from the same user grouped together, and within each group, events sorted by time so close pairs are adjacent. A lexicographic sort by (user, timestamp) — meaning sort by user first, break ties by timestamp — achieves both goals in one pass. Once sorted, all of user Alice's records appear consecutively and in chronological order, then all of Bob's, and so on. You only need to walk through the list and, for each record, check whether timestamp[i] - timestamp[i-1] <= D and user[i] == user[i-1]. That's the logic behind answer C, and it's correct. Answer A fails because sorting by timestamp alone interleaves all users together. Neighboring records may belong to different users entirely, so a small timestamp difference between record $i$ and record $i-1$ doesn't indicate a single-user violation. Answer B sorts by user correctly — grouping each user's events — but leaves timestamps in arbitrary order within each block. Two events that are only $1$ time unit apart might be at opposite ends of that block, so a simple adjacent comparison would miss them entirely. Answer D sorts by timestamp first, then user. This primarily orders events chronologically across all users, not per-user chronologically. The "equal user blocks" it describes don't form a complete, time-ordered history; they're just timestamp-tied clusters. A good study tip: when a problem requires two grouping criteria, ask yourself which criterion should be the primary sort key and which should be secondary — the answer usually reveals the correct algorithm.

Start this quiz