//

//  main.cpp

//  greedy

#include <iostream>

using std::cout;

using std::cin;

using std::string;

#define SIZEOF_ARRAY(a) (sizeof(a)/sizeof(a[0]))

template<typename T>

void insertion_sort(T *a, size_t n) {

    T tmp;

    size_t j, p;

    for (p = 1; p < n; p++) {

        tmp = a[p];

        for (j = p; 0 < j && tmp < a[j-1]; j--) {

            a[j] = a[j-1];

        }

        a[j] = tmp;

    }

}

template<typename T>

void swap(T *a, T *b) {

    T tmp = *a;

    *a = *b;

    *b = tmp;

}

// Return median of "left", "center", and "right"

// Order these and hide the pivot

template<typename T>

T median3(T *a, size_t left, size_t right) {

    size_t center = (left+right)/2;

    if (a[left] > a[center])

        swap(&a[left], &a[center]);

    if (a[left] > a[right])

        swap(&a[left], &a[right]);

    if (a[center] > a[right])

        swap(&a[center], &a[right]);

    /* Invariant: a[left]<=a[center]<=a[right] */

    swap(&a[center], &a[right-1]); /* HIde pivot */

    return a[right-1]; /* return pivot */

}

#define cutoff (3)

template<typename T>

void quicksort(T *a, size_t left, size_t right) {

    size_t i, j;

    T pivot;

    if (left + cutoff <= right) {

        pivot = median3(a, left, right);

        i = left;

        j = right-1;

        for (;;) {

            while (a[++i] < pivot) {}

            while (a[--j] > pivot) {}

            if (i < j)

                swap(&a[i], &a[j]);

            else

                break;

        }

        swap(&a[i], &a[right-1]); /* restore pivot */

        quicksort(a, left, i-1);

        quicksort(a, i+1, right);

    } else {

        insertion_sort(a+left, right-left+1);

    }

}

template<typename T>

void sort(T *a, size_t n) {

    quicksort(a, 0, n-1);

}

template<typename T>

void print_array(T *a, size_t n) {

    size_t i;

    cout << "[";

    for (i = 0; i < n-1; i++) {

        cout << a[i] << ",";

    }

    cout << a[i] << "]\n";

}

int scheduling(int *a, size_t n, int t) {

    int numberOfThings = 0, currentTime = 0;

    sort<int>(a, n);

    print_array<int>(a, n);

    for (int i = 0; i < n; i++) {

        currentTime += a[i];

        if (currentTime > t) {

            break;

        }

        numberOfThings++;

    }

    return numberOfThings;

}

int main(int argc, const char * argv[]) {

    int a[] = {15, 17, 15, 18, 10};

    int t = 40, n = SIZEOF_ARRAY(a);

    cout << "the Scheduling problem output: "<< scheduling(a, n, t) << "\n";

    return 0;

}