SushiNori: Shift Scheduling

README.md

SushiNori: Shift Scheduling

SushiNori has a team of chefs to work its two chef stations. The chefs make requests to management for days they prefer to have off each week. You've been asked to determine whether it's possible to arrange the weekly schedule in such a way that all chefs will get to take their preferred days off while keeping the restaurant staffed.

SushiNori is open seven days a week. Each workday consists of two shifts of 8 hours each. There are restrictions on how many hours employees may work:

• No employee may log more than 40 hours in a week.
• No employee may exceed 5 days of work in a week.
• No employee may work more than 8 hours in a day.

Your task

Complete the function boolean schedulable(HashMap > requests); where requests is a HashMap mapping each chef name to a list of days that chef has requested off for this week: The string days of the week are guaranteed to be chronologically sorted. Return true if it's possible to schedule all chefs such that all shifts are covered and all chefs' requests for days off are satisfied and false otherwise.

Examples

• Example 1

HashMap  > requests = new HashMap<>(); 
requests.put( "ada", new ArrayList<>(Arrays.asList( new String[] {"mon", "tue", "wed", "fri", "sat", "sun"} )) );
requests.put( "emma", new ArrayList<>(Arrays.asList( new String[] {"tue", "wed", "thu", "sun"} )) );
requests.put( "remy", new ArrayList<>(Arrays.asList( new String[] {"mon", "sat"} )) );
requests.put( "zach", new ArrayList<>(Arrays.asList(new String[] {})) );

ChefScheduler.schedulable(requests);

This call to schedulable should return true. Monday has been requested off by two chefs, for example, but Emma and Zach can cover. No chef will be overworked. Here is a possible schedule (all shifts are 8 hours):

Monday : Emma, Zach 
Tuesday : Zach, Remy 
Wednesday : Zach, Remy 
Thursday : Remy, Ada 
Friday : Remy, Emma 
Saturday : Emma, Zach 
Sunday : Zach, Remy

• Example 2

HashMap  > requests = new HashMap<>();
requests.put( "emma", new ArrayList<>(Arrays.asList( new String[] {"sun"} )) );
requests.put( "remy", new ArrayList<>(Arrays.asList( new String[] {"sun"} )) );
requests.put( "zach", new ArrayList<>(Arrays.asList(new String[] {})) );

ChefScheduler.schedulable(requests);

This call to schedulable should return false because Zach will be unable to cover Sunday alone.

• Example 3

HashMap  > requests = new HashMap<>();
requests.put( "ada", new ArrayList<>(Arrays.asList( new String[] {"mon", "tue", "wed", "thu", "fri", "sat"} )) );
requests.put( "emma", new ArrayList<>(Arrays.asList( new String[] {"tue", "wed", "thu", "sun"} )) );
requests.put( "remy", new ArrayList<>(Arrays.asList( new String[] {"mon", "fri", "sun"} )) );
requests.put( "zach", new ArrayList<>(Arrays.asList(new String[] {})) );

ChefScheduler.schedulable(requests);

This call to schedulable should return false because Zach would have to work in excess of 5 days in order to cover all needed shifts.

ShiftScheduling.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.CopyOnWriteArrayList;

public class ChefScheduler {
    private final static List<String> days = List.of("mon", "tue", "wed", "thu", "fri", "sat", "sun");

    public static boolean schedulable(
            Map<String, List<String>> requests
    ) {
        Map<String, List<String>> employeePerWorkDays = new HashMap<>();
        Map<String, Set<String>> workDaysPerEmployee = new HashMap<>();

        for (String employeeName : requests.keySet()) {
            List<String> freeDays = requests.get(employeeName);

            List<String> workDays = new CopyOnWriteArrayList<>(days);
            workDays.removeAll(freeDays);
            for (String workDay : workDays) {
                Set<String> employees = workDaysPerEmployee.computeIfAbsent(workDay, (res) -> new HashSet<>());
                employees.add(workDay);
            }

            // Save possible work days
            employeePerWorkDays.put(employeeName, workDays);
        }

        for (String employeeName : requests.keySet()) {
            List<String> workDays = employeePerWorkDays.get(employeeName);

            if (workDays.size() > 5) {
                // Possibility to reduce days
                for (String workDay : workDays) {
                    Set<String> employees = workDaysPerEmployee.get(workDay);
                    if (employees.size() > 2) {
                        employees.remove(employeeName);

                        // Save
                        workDays.remove(workDay);
                    }
                }
            }

            // Save work days
            employeePerWorkDays.put(employeeName, workDays);
        }

        // Check for overworked
        for (String day : days) {
            int nbEmployeePerDay = workDaysPerEmployee.get(day).size();

            if (!(nbEmployeePerDay == 2)) {
                return false;
            }
        }

        return employeePerWorkDays.values().stream().noneMatch(workDays -> workDays.size() > 5);
    }
}