20-CS-122-001 Computer Science II Spring 2012
Maximum Cardinality (Size) Subset

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Given: a list of n positive integers, not necessarily in any order.
Implement: A function that takes this list as input and outputs an array arr such that 1) a subset (or maybe all) of the input numbers are in arr; 2) for all 0 ≤ i < n, arr[i] < i; 3) the subset of the input list is the maximum cardinality (size) subset for which 2) holds.

This is just Integer Deadline Scheduling in disguise - set all profits to 1.