activity_selection_code.cpp

#include <iostream>
using namespace std;

const int MAX = 100;

struct Activity {
    int id;
    int start;
    int finish;
};

void merge(Activity arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    Activity L[MAX], R[MAX];

    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }

    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = left;

    while (i < n1 && j < n2) {

        if (L[i].finish <= R[j].finish) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }

        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void sortByFinishTime(Activity arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;

        sortByFinishTime(arr, left, mid);

        sortByFinishTime(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int activitySelection(Activity activities[], int n,
                      int selectedIds[], int &selectedCount) {

    sortByFinishTime(activities, 0, n - 1);

    selectedCount = 0;

    selectedIds[selectedCount] = activities[0].id;
    selectedCount++;

    int lastFinish = activities[0].finish;

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

        if (activities[i].start >= lastFinish) {

            selectedIds[selectedCount] = activities[i].id;
            selectedCount++;

            lastFinish = activities[i].finish;
        }
    }

    return selectedCount;
}

int readActivities(Activity activities[]) {

    int n;

    cout << "Enter the number of activities: ";
    cin >> n;

    cout << "\nEnter start and finish time for each activity:\n";

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

        activities[i].id = i + 1;

        cout << "  Activity " << i + 1 << " -> Start: ";
        cin >> activities[i].start;

        cout << "              Finish: ";
        cin >> activities[i].finish;
    }

    return n;
}

void printActivities(Activity activities[], int n) {

    cout << "\n------------------------------------------\n";
    cout << "  ID   Start   Finish\n";
    cout << "------------------------------------------\n";

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

        cout << "   "
             << activities[i].id
             << "     "
             << activities[i].start
             << "       "
             << activities[i].finish
             << "\n";
    }

    cout << "------------------------------------------\n";
}

void printSelected(int selectedIds[], int count) {

    cout << "\nMaximum number of activities that can be selected: "
         << count << "\n";

    cout << "Selected activity IDs (in order of finish time): ";

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

        if (i != 0)
            cout << ", ";

        cout << selectedIds[i];
    }

    cout << "\n";
}

int main() {

    Activity activities[MAX];

    int selectedIds[MAX];

    int selectedCount = 0;

    cout << "======================================\n";
    cout << "   Activity Selection  -  Greedy\n";
    cout << "======================================\n\n";

    int n = readActivities(activities);

    cout << "\nActivities before sorting:\n";
    printActivities(activities, n);

    activitySelection(activities, n,
                      selectedIds, selectedCount);

    cout << "\nActivities after sorting by finish time:\n";
    printActivities(activities, n);

    printSelected(selectedIds, selectedCount);

    cout << "\n======================================\n";
    cout << "  Complexity: O(n log n)\n";
    cout << "======================================\n";

    return 0;
}