Approach or algorithm to check single meeting room time table availability for 3 same rooms?

Question

If I would like to provide a calendar-like time table with time slot unit 30 minutes for meeting rooms booking.

One single time table to represent 3 real meeting rooms availability. Suppose this booking meeting room is called A and 3 real rooms are A1, A2, A3.

Everyone is limited to book fixed 3 hours, what's the better approach to check and represent "the current meeting room availability"?

E.g.

Some one had booked A1 from 01:00 ~ 04:00

Some one had booked A2 from 02:00 ~ 05:00

Some one had booked A3 from 03:00 ~ 06:00

So booking interval 00:00 ~ 03:00 is available, 05:00 ~ 08:00 is also available, but 01:00~ 04:00 is not.

How to check the meeting room time table A with precise available time slots intervals?

Answer 1

What you are asking for is a rather frequently asked question - merge the intervals to locate the free/available slots.

I just can provide a demo for you to solve this kind of interval merging problems in java 8 using LocalDate, you can just replace it with LocalTime as required.

And also since you have several rooms, you need to modify the intervals a little bit to blend in.

Demo and test cases:

public class Extra_1_interval_merge {
    @Test
    public void testAvailablePeriod() {
        List<MyPeriod> absentPeriods0 = new ArrayList<>();
        absentPeriods0.add(makePeriod(LocalDate.now(), LocalDate.now().plusDays(1)));
        absentPeriods0.add(makePeriod(LocalDate.now().plusDays(4), LocalDate.now().plusDays(6)));
        absentPeriods0.add(makePeriod(LocalDate.now().plusDays(2), LocalDate.now().plusDays(3)));


        List<MyPeriod> absentPeriods1 = new ArrayList<>();
        absentPeriods1.add(makePeriod(LocalDate.now(), LocalDate.now().plusDays(2)));
        absentPeriods1.add(makePeriod(LocalDate.now().plusDays(5), LocalDate.now().plusDays(7)));

        List<List<MyPeriod>> absentListList = new ArrayList<>();
        absentListList.add(absentPeriods0);
        absentListList.add(absentPeriods1);
        System.out.println(getAvailablePeriods(absentListList));
    }

    private List<MyPeriod> getAvailablePeriods(List<List<MyPeriod>> absentListList) {
        // Step - 1: Collect all periods;
        List<MyPeriod> tempList = new ArrayList<>();
        absentListList.stream().forEach(list -> tempList.addAll(list));

        // Step - 2: Sort the periods based on the startDate and then endDate;
        List<MyPeriod> absentList = tempList.stream().sorted((period1, period2) -> {
            if (!period1.startDate.isEqual(period2.startDate)) {
                return period1.startDate.compareTo(period2.startDate);
            } else {
                return period1.endDate.compareTo(period2.endDate);
            }
        }).collect(toList());

        // Step - 3: Merge all overlapped periods to form an one-dimension occupied period list;
        List<MyPeriod> mergedPeriods = new ArrayList<>();
        for (MyPeriod period : absentList) {
            if (mergedPeriods.isEmpty()) {
                mergedPeriods.add(period);
            } else {
                MyPeriod lastPeriod = mergedPeriods.get(mergedPeriods.size() - 1);
                if (!lastPeriod.endDate.isBefore(period.startDate)) {
                    if (lastPeriod.endDate.isBefore(period.endDate)) {
                        lastPeriod.endDate = period.endDate;
                    }
                } else {
                    mergedPeriods.add(period);
                }
            }
        }

        // Step - 4: Pick the periods from the occupied period list;
        List<MyPeriod> availablePeriods = new ArrayList<>();
        for (int i = 0, len = mergedPeriods.size(); i < len - 1; i++) {
            availablePeriods.add(makePeriod(mergedPeriods.get(i).endDate, mergedPeriods.get(i+1).startDate));
        }
        return availablePeriods;
    }

    private MyPeriod makePeriod(LocalDate startDate, LocalDate endDate) {
        MyPeriod thePeriod = new MyPeriod();
        thePeriod.startDate = startDate;
        thePeriod.endDate = endDate;
        return thePeriod;
    }

    class MyPeriod {
        LocalDate startDate;
        LocalDate endDate;
        @Override
        public String toString() {
            return String.format("Start: %s, End: %s", startDate, endDate);
        }
    }

}