Least # of Activities

#Airbnb #Medium #DynamicProgramming

Question

Given a list of activities, find the minimum # of activities to fully occupy the target time. You can repeat the same activity more than once.

Solution‌

Use dynamic programming to calculate the minimum # of activities required to fully spend the target hours. Start from hour 0.

int findMinimumActivities(List<Activity> activities, int target) {

    // Used to record minimum # of activities to fully spend every hours
    // up to the given target.
    // - key: hour
    // - value: minimum # of activities to fully spend "key" hour.
    //
    // E.g., {5, 3} means the minimum # of activities to fully spend 5
    // hours is 3.
    //
    // Note: It does not contain any hours that is not possible to fully
    // spend with the given list of activities.
    Map<Integer, Integer> minActivitiesCountMap = new HashMap<>();

    // Initial state: you need 0 activity to spend 0 hour.
    minActivitiesCountMap.put(0, 0);

    // Use dynamic programming to calculate the minimum # of activities
    // required to fully spend the target hours.
    for (int hour = 1; hour <= target; hour++) {
        // A variable to keep track of the minimum # of activities
        // to fully spend the current "hour."
        int minActivities = Integer.MAX_VALUE;

        // Iterate through the list of given activities and find the
        // minimum # of activities count.
        for (Activity activity : activities) {
            int remainingHours = hour - activity.hour;
            if (minActivitiesCountMap.containsKey(remainingHours)) {
                int count = minActivitiesCountMap.get(remainingHours) + 1;
                minActivities = Math.min(count, minActivities);
            }
        }

        // If we weren't able to find a combination of activities to
        // fully spend the "current" hour, do not put record in the map.
        if (minActivities != Integer.MAX_VALUE) {
            minActivitiesCountMap.put(hour, minActivities);
        }
    }

    return minActivitiesCountMap.getOrDefault(target, -1);
}