0
$\begingroup$

I am learning the Interval scheduling problem, and I came up after some reading with an implementation. I'll list my steps and the code, please let me know if this is correct or there is a more optimise way.

Problem: I have one resource and a list of tasks. The goal is execute these tasks in a way that makes the number of tasks waiting to be executed minimal.

Algorithm:

  1. Create two sets of tasks. A is the set of tasks. B is a set of incompatible tasks.

  2. Initiate A with all tasks that you have at the beginning of the solution.

  3. pick up from A the soonest to finish task, let's call it T.

  4. remove from A all the incompatible tasks to T and put them in B.

  5. go back to step number 3 and repeat until A is empty.

  6. Move all tasks from B to A.

  7. Go back to step number 3.

  8. Go back to step number 6 until B is empty.

Implementations:

I chose Map data structure to represents both A and B because look up is of O(1).

import java.sql.Timestamp;
import java.time.Instant;
import java.util.*;
import java.util.stream.Collectors;

public class First {
    public static void main(String[] args) {
        List<Task> tasks = new LinkedList<>();
        tasks.add(new Task("Cleaning",
                Timestamp.from(Instant.parse("2020-07-25T08:00:00.000Z")),
                Timestamp.from(Instant.parse("2020-07-25T09:00:00.000Z"))));
        tasks.add(new Task("Washing clothes"
                , Timestamp.from(Instant.parse("2020-07-25T09:00:00.000Z"))
                , Timestamp.from(Instant.parse("2020-07-25T10:00:00.000Z"))));
        tasks.add(new Task("Playing",
                Timestamp.from(Instant.parse("2020-07-25T09:30:00.000Z")),
                Timestamp.from(Instant.parse("2020-07-25T10:30:00.000Z"))));
        List<Task> results = solve(tasks, new Resource());
        results.stream()
                .forEach(task -> {
                    System.out.println(String.format("Task %d:%s starts at %s, ends at %s",
                            task.getId(),
                            task.getName(),
                            task.getStartTime(),
                            task.getEndTime()));
                });
    }

    /**
     * 1- pick up the next one.
     * 2- remove all none compatible tasks.
     * 3- repeat.
     *
     * @param tasks
     * @param resource
     * @return
     */
    private static List<Task> solve(List<Task> tasks, Resource resource) {
        Map<Integer, Task> map = tasks.stream()
                .collect(Collectors.toMap(task -> task.getId(), task -> task));
        return solve(map, new HashMap<>(), resource);
    }

    private static List<Task> solve(Map<Integer, Task> tasks,
                                    Map<Integer, Task> noneCompatibleTasks,
                                    Resource resource) {
        if (tasks.isEmpty()) {
            if (noneCompatibleTasks.isEmpty()) {
                return new LinkedList<>();
            } else {
                return solve(noneCompatibleTasks, new HashMap<>(), resource);
            }
        } else {
            Task task = getSoonestFinishTask(tasks);
            tasks.remove(task.getId());
            List<Task> noneCompatibleTasksTo = noneCompatibleTasksTo(tasks, task);
            noneCompatibleTasksTo.forEach(t -> noneCompatibleTasks.put(t.getId(), t));
            noneCompatibleTasksTo.forEach(t -> tasks.remove(t.getId()));
            List<Task> results = new LinkedList<>();
            results.add(task);
            results.addAll(solve(tasks, noneCompatibleTasks, resource));
            return results;
        }
    }

    private static List<Task> noneCompatibleTasksTo(Map<Integer, Task> tasks, Task task) {
        List<Task> results = new LinkedList<>();
        Iterator<Integer> iterator = tasks.keySet().iterator();
        while (iterator.hasNext()) {
            int id = iterator.next();
            if (tasks.get(id).getStartTime().compareTo(task.getEndTime()) > 0) {
                results.add(tasks.get(id));
            }
        }
        return results;
    }

    private static Task getSoonestFinishTask(Map<Integer, Task> map) {
        if (map == null || map.isEmpty()) {
            throw new RuntimeException("Shouldn't be called on an empty input.");
        }
        Task result = null;
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            int id = iterator.next();
            if (result == null) {
                result = map.get(id);
            } else {
                Task task = map.get(id);
                if (result.getEndTime().compareTo(task.getEndTime()) > 0) {
                    result = task;
                }
            }
        }
        return result;
    }
}

This is my Task definition.

@Value
public class Task {
    private static int numberOfTasks = 0;
    private final int id = ++numberOfTasks;
    private final String name;
    private final Timestamp startTime;
    private final Timestamp endTime;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.