Answer to Question #309857 in C for Mohammed

Question

Harold and his homework

Harold and Dan are friends and study in the same class. One day, they strike a deal about completing Harold's homework.

The deal is that, for every piece of homework belonging to Harold which Dan completes, Harold will give Dan some money. The catch is that every piece of homework has a deadline associated with it and has to be completed within that deadline only.

It takes 1 unit amount of time to complete a homework. You have to help Dan find and return the maximum money he can earn.

Input Specification:

input1: The number of tasks

input2: An array representing money associated with each task input3: An array representing the deadline of each task

Output Specification:

Your function must return the maximum amount of money Dan can earn

Example 1:

input1: 3

input2: (20,54,41)

input3: (3,4,5)

Output: 115

Explanation:

Here, all the homework can be done as all have different deadlines and so maximum money is the sum of 20+54+41= 115.

Answer 1

#include <stdio.h>
#define N 100


int max_homework(int money[], int deadline[], int n) {
    int indx[N];
    int i, j, k, i_min;
    int sum, max_m;


    for (i=0; i<n; i++) {
        indx[i] = i;
    }


    for (i=0; i<n-1; i++) {
        i_min = i;
        for (j=i+1; j<n; j++) {
            if (deadline[i_min] > deadline[j]) {
                i_min = j;
            }
        }
        k = indx[i_min];
        indx[i_min] = indx[i];
        indx[i] = k;
    }


    sum = 0;
    i = 1;
    max_m = money[indx[0]];
    while (i<n) {
        if (deadline[indx[i-1]] != deadline[indx[i]]) {
            sum += max_m;
            max_m = money[indx[i]];
        }
        else {
            if (money[indx[i]] > max_m) {
                max_m = money[indx[i]];
            }
        }
        i++;
    }
    sum += max_m;


    return sum;
}


int main() {
    int money[N];
    int deadline[N];
    int i, n, m;

    scanf("%d", &n);
    if (n > N) {
        fprintf(stderr, "N is too big\n");
        return 1;
    }
    for (i=0; i<n; i++) {
        scanf("%d", &money[i]);
    }
    for (i=0; i<n; i++) {
        scanf("%d", &deadline[i]);
    }

    m = max_homework(money, deadline, n);
    printf("%d", m);
}