Employee Free Time - rFronteddu/general_wiki GitHub Wiki

Employee Free Time — Problem Description

You are given a list of employees, and for each employee, you are provided a list of non-overlapping, sorted working intervals. Your task is to find the common free time intervals shared by all employees.

A free time interval is defined as a finite interval during which every employee is not working.

  • Input A list schedule where:
    • schedule[i] represents the working intervals of the i-th employee.
    • Each employee’s intervals are Sorted by start time and Non-overlapping within that employee’s schedule.
import java.util.*;
class Main {
    static void solve(List<List<int[]>> input, List<int[]> expected) {
        // add to one interval, sort, merge, gaps are free times
        if(input.size() <= 1) {
            System.out.println("Results: ");
            System.out.println("Expected: ");
            for(var x : expected) {
                System.out.println("\t" + x[0] + " " + x[1]);
            }
            return;
        }
        // add
        List<int[]> added = new ArrayList<>();
        for (var x : input) {
            for(var y : x) {
                added.add(y);
            }
        }
        // sort
        Collections.sort(added, Comparator.comparingInt(a -> a[0]));

        List<int[]> merged = new ArrayList<>();
        merged.add(new int[]{added.get(0)[0], added.get(0)[1]});
        for(int i = 1; i < added.size(); i++) {
            var last = merged.get(merged.size() - 1);
            var curr = added.get(i);
            //System.out.print("Last: " + last[0] + " " + last[1] + " ");
            //System.out.println("Curr: " + curr[0] + " " + curr[1]);
            
            if(curr[0] <= last[1]) {
                last[1] = Math.max(curr[1], last[1]);
            } else {
                merged.add(curr);
            }
        }
        
        List<int[]> result = new ArrayList<>();
        for(int i = 1; i < merged.size(); i++) {
            if(merged.get(i-1)[1] != merged.get(i)[0]) {
                // we have a gap
                result.add(new int[]{merged.get(i-1)[1],merged.get(i)[0]});
            }
        }
        System.out.println("Results: ");
        for(var x : result) {
           System.out.println("\t" + x[0] + " " + x[1]);
        }
        System.out.println("Expected: ");
        for(var x : expected) {
           System.out.println("\t" + x[0] + " " + x[1]);
        }
    }
    
    
    public static void main(String[] args) {
        List<List<List<int[]>>> testCases = new ArrayList<>();
        List<List<int[]>> answers = new ArrayList<>();

        // Test Case 1
        testCases.add(Arrays.asList(
                Arrays.asList(new int[]{1,2}, new int[]{5,6}),
                Arrays.asList(new int[]{1,3}),
                Arrays.asList(new int[]{4,10})
        ));
        answers.add(Arrays.asList(
                new int[]{3,4}
        ));


        // Test Case 2
        testCases.add(Arrays.asList(
                Arrays.asList(new int[]{1,3}, new int[]{6,7}),
                Arrays.asList(new int[]{2,4}),
                Arrays.asList(new int[]{2,5}, new int[]{9,12})
        ));
        answers.add(Arrays.asList(
                new int[]{5,6},
                new int[]{7,9}
        ));

        // Test Case 3
        testCases.add(Arrays.asList(
                Arrays.asList(new int[]{1,5}),
                Arrays.asList(new int[]{2,6}),
                Arrays.asList(new int[]{3,7})
        ));
        answers.add(new ArrayList<>());  // []

        // Test Case 4
        testCases.add(Arrays.asList(
                Arrays.asList(new int[]{1,3}, new int[]{6,8})
        ));
        answers.add(new ArrayList<>());  // []

       for(int i = 0; i < testCases.size(); i++) {
           System.out.print("Experiment " + i + " ");
           solve(testCases.get(i), answers.get(i));
       }

    }
}
⚠️ **GitHub.com Fallback** ⚠️