algorithm-examples/cpp-algorithm/src/greedy/activity_selection.h at main · codejsha/algorithm-examples · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#ifndef CPP_ALGORITHM_ACTIVITY_SELECTION_H
#define CPP_ALGORITHM_ACTIVITY_SELECTION_H

#include <vector>

namespace ActivitySelection
{
    /**
     * \brief Activity selection problem using recursive approach.
     * \param start start times of activities
     * \param finish finish times of activities
     * \param index index of activity
     * \param size size of activities
     * \return the resulting set of selected activities
     */
    std::vector<int> RecursiveActivitySelector(
        const std::vector<int>& start,
        const std::vector<int>& finish,
        int index,
        int size);

    /**
     * \brief Activity selection problem using greedy algorithm.
     * \param start start times of activities
     * \param finish finish times of activities
     * \return the resulting set of selected activities
     */
    std::vector<int> GreedyActivitySelector(
        const std::vector<int>& start,
        const std::vector<int>& finish);
}

// ----------------------------------------------------------------------------
inline std::vector<int> ActivitySelection::RecursiveActivitySelector(
    const std::vector<int>& start,
    const std::vector<int>& finish,
    const int index,
    const int size)
{
    int sub_index = index + 1;

    while ((sub_index < size) && (start[sub_index] < finish[index]))
    {
        ++sub_index;
    }

    if (sub_index < size)
    {
        std::vector<int> activities = RecursiveActivitySelector(start, finish, sub_index, size);
        activities.push_back(sub_index);

        return activities;
    }
    return {};
}

// ----------------------------------------------------------------------------
inline std::vector<int> ActivitySelection::GreedyActivitySelector(
    const std::vector<int>& start,
    const std::vector<int>& finish)
{
    const int size = static_cast<int>(start.size());
    std::vector<int> selected;

    selected.push_back(0);

    int index = 0;
    for (int i = 1; i < size; ++i)
    {
        if (start[i] >= finish[index])
        {
            selected.push_back(i);
            index = i;
        }
    }

    return selected;
}

#endif