CODEWITHSUNDEEP
javaalgorithmdistributionmathematical-optimizationnumerical-methods
Akila
Akila

Reputation: 187

Equal distributing algorithm

I am working on developing an Event distribution application. I have an large list of events for a month. Events objects contains start and end times. 

public class Event {
    long eventID;

    Calendar startTime;
    Calendar endTime;

    .......
}

I want to separate above list into N number of parts. 

Map<Integer, List<Event>> eventLists;

The requirements are : size of the each blocks should be nearly equal and the distribution of the each parts should distribute equally in the month.

Is there any well known algorithm that suits to solve this problem. I would prefer, if someone could provide an accurate solution or any reference to any well known algorithm.

I'm looking for an algorithm with statistical analysis.

this is an simple example what I seeking for. But it should contains statistical analysis to distribute equal.

Calendar monthStart = EventUtil.getMonthStart();
Calendar monthEnd = EventUtil.getMonthEnd();

Calendar oneDayRange = Calendar.getInstance();
oneDayRange.add(Calendar.DATE, 1);

int index = 0;

while (!monthStart.after(monthEnd)) {

    Iterator<Event> it = events.iterator();

    while (it.hasNext()) {
        Event e = it.next();

        if(!e.getStartTime().before(monthStart) && !e.getStartTime().after(oneDayRange)) {
            eventLists.get(index % N).add(e);
            it.remove();
            index++;
        }

    }

    monthStart.add(Calendar.DATE, 1);
    oneDayRange.add(Calendar.DATE, 1);
}

thanks a lot!

Upvotes: 0

Views: 732

Answers (1)

Codor
Codor

Reputation: 17595

If the event duration has to be taken into account, the problem described is a generalization of the partition problem, which is NP-hard, but admits a polynomial time approximation scheme. If the event durations are not important and a round-robin assignment to the N slots can be done in linear time.

Upvotes: 1

Related Questions