Scheduling and coin change greedy algorithms implemented in c++11

greedy.cpp

#include <algorithm>
#include <chrono>
#include <vector>
#include <map>
#include <iostream>
#include <tuple>
#include <string>
#include <ctime>

namespace chrono = std::chrono;
typedef std::chrono::system_clock Clock;
typedef Clock::time_point Time;
typedef std::tuple<std::string, Time, Time> Event;
typedef std::vector<Event> Events;

std::map<double, int> coin_change(double change, std::vector<double> denominations)
{
    std::map<double, int> coin_map;

    for (double d : denominations)
    {
        while (change > d)
        {
            change -= d;
            coin_map[d] = coin_map[d] + 1;
        }
    }

    return coin_map;
}

Events schedule(Events all)
{
    Events solution;

    // sort the events by earliest ending time
    std::sort(all.begin(), all.end(), [] (Event l, Event r) 
        {
            Time l_end = std::get<2>(l);
            Time r_end = std::get<2>(r);

            if (l_end <= r_end)
                return true;

            return false;
        });

    for (Event e : all)
    {
        Time start = std::get<1>(e);
        Time end = std::get<2>(e);

        // assume this event is compatible
        bool compatible = true;

        for (Event s : solution)
        {
            Time s_start = std::get<1>(s);
            Time s_end = std::get<2>(s);

            compatible = compatible &&
                ((start < s_start && end <= s_start) || 
                 (start >= s_end && end > s_end));
        }

        if (compatible)
        {
            solution.push_back(e);
        }
    }

    return solution;
}

int main()
{
    std::map<double, int> change = coin_change(0.83, { 0.25, 0.1, 0.05, 0.01 });
    for (auto coin : change)
        std::cout << coin.first << ": " << coin.second << std::endl;
    
    Time now = Clock::now();

    Events classes = { 
        std::make_tuple("Computer Logic", now - chrono::hours(1), now - chrono::minutes(15)),
        
        std::make_tuple("Discrete Structures", now - chrono::hours(2), 
            now - chrono::hours(1) - chrono::minutes(10)),
            
        std::make_tuple("Computer Science", now, now + chrono::minutes(50)),
        // this event won't get scheduled:
        std::make_tuple("OO Programming", now - chrono::minutes(20), now + chrono::minutes(30))
    };

    classes = schedule(classes);

    std::cout << std::endl << "Generated schedule: " << std::endl;

    for (Event e : classes)
    {
        std::string course = std::get<0>(e);
        Time start = std::get<1>(e);
        Time end = std::get<2>(e);

        // Convert start and end to time_t for easy printing
        std::time_t t_start = Clock::to_time_t(start);
        std::time_t t_end = Clock::to_time_t(end);
        
        std::cout << "Event: " << course << std::endl;
        std::cout << "Starts: " << std::ctime(&t_start);
        std::cout << "Ends: " << std::ctime(&t_end);
        std::cout << "Duration: " << chrono::duration_cast<chrono::minutes>(end - start).count() <<
            " minutes" << std::endl << std::endl;
    }
    
    return 0;
}