البحث عن خوارزمية لتخطيط لافتات أحداث التقويم بكفاءة

Question

أنا أبحث عن خوارزمية لوضع لافتات الأحداث طوال اليوم/متعددة الأيام بكفاءة، تمامًا مثل طريقة عرض الشهر في Outlook أو تقويم Google.لدي عدد من الأحداث بتاريخ البدء والانتهاء، مرتبة حسب زيادة تاريخ البدء (ثم الانتهاء) (أو أي ترتيب آخر تفضله، فأنا أقوم بجمع الأحداث من جدول قاعدة البيانات).أرغب في تقليل متوسط ​​المساحة الرأسية المستخدمة، لأنه بعد لافتات الحدث سأحتاج إلى وضع أحداث أخرى لذلك اليوم فقط (تأتي هذه الأحداث دائمًا بعد اللافتات الخاصة بتاريخ معين).لذا، على سبيل المثال، إذا كان لدي حدثان، أحدهما 1/10-1/11 والآخر 1/11-1/15، فإنني أفضل ترتيبهما على هذا النحو (كل عمود يمثل يومًا واحدًا):

 bbbbb
aa

وليس مثل:

aa
 bbbbb

لأنه عندما أقوم بإضافة أحداث اليوم فقط (x، y، وz)، يمكنني القيام بذلك (أفضل الأول، لا أريد الثاني):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

لكن الأمر ليس بهذه البساطة مثل وضع الأحداث الأطول أولاً، لأنه مع 1/10-1/11، و1/13-1/14، و1/11-1/13، أريد:

aa cc
 bbb

في مقابل:

 bbb
aa cc

لأن هذا من شأنه أن يسمح للأحداث x و y:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

وبالطبع أفضّل أن أفعل ذلك دفعة واحدة.بالنسبة لبنية البيانات، أستخدم حاليًا خريطة من تاريخ إلى قائمة، حيث أقوم بإضافة الحدث إلى القائمة المقابلة لكل يوم من أيام الحدث.لذلك يظهر حدث مدته ثلاثة أيام في ثلاث قوائم، كل واحدة منها تقع ضمن أحد الأيام الموجودة على الخريطة.هذه بنية مناسبة لتحويل النتيجة إلى مخرجات مرئية، لكنني منفتح على هياكل البيانات الأخرى أيضًا.أستخدم حاليًا خوارزمية جشعة، حيث أقوم فقط بإضافة كل حدث بالترتيب، ولكن يمكن أن ينتج عن ذلك عناصر غير مرغوب فيها مثل:

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

وهذا يضيع أ كثير مساحة لمعظم أيام الحدث "e".

أيه أفكار؟

Answer 1

فيما يلي رسم تخطيطي عالي المستوى لأحد الحلول الممكنة (باستخدام الأعداد الصحيحة لأيام الأسبوع بدلاً من التواريخ الكاملة).هذه الواجهة:

public interface IEvent {

    public abstract int getFirst();  // first day of event
    public abstract int getLast();   // last day of event
    public abstract int getLength(); // total number of days
    public abstract char getLabel(); // one-char identifier

    // true if this and that have NO days in common
    public abstract boolean isCompatible(IEvent that);

    // true if this is is compatible with all events
    public abstract boolean isCompatibleWith(Collection<IEvent> events);

}

يجب تنفيذها لاستخدام الخوارزمية المعبر عنها في layout الطريقة أدناه.

بالإضافة إلى ذلك، يجب تنفيذ الطبقة الملموسة Comparable لإنشاء نظام طبيعي حيث تسبق الأحداث الأطول الأحداث الأقصر.(استخدم نموذج التنفيذ الخاص بي للعرض التوضيحي أدناه ترتيبًا تنازليًا للطول، ثم تاريخ البدء التصاعدي، ثم التصنيف التصاعدي.)

ال layout الطريقة تأخذ مجموعة من IEvent الحالات والعوائد أ Map الذي يعين لكل صف في العرض التقديمي مجموعة الأحداث التي يمكن عرضها في هذا الصف.

public Map<Integer,Set<IEvent>> layout(Collection<IEvent> events) {
    Set<IEvent> remainingEvents = new TreeSet<IEvent>(events);
    Map<Integer,Set<IEvent>> result = new TreeMap<Integer,Set<IEvent>>();
    int day = 0;
    while (0 < remainingEvents.size()) {
        Set<IEvent> dayEvents = new TreeSet<IEvent>();
        for(IEvent e : remainingEvents) {
            if (e.isCompatibleWith(dayEvents)) {
                dayEvents.add(e);
            }
        }
        remainingEvents.removeAll(dayEvents);
        result.put(day, dayEvents);
        ++day;
    }
    return result;
}

يتكون كل صف عن طريق تحديد الحدث الأطول المتبقي والاختيار التدريجي لجميع الأحداث الإضافية (بالترتيب الموضح أعلاه) المتوافقة مع الأحداث المحددة مسبقًا للصف الحالي.والنتيجة هي أن جميع الأحداث "تطفو" لأعلى قدر الإمكان دون تصادم.

يعرض العرض التوضيحي التالي السيناريوهين في سؤالك، بالإضافة إلى مجموعة من الأحداث التي تم إنشاؤها عشوائيًا.

Event collection:
    x(1):4
    b(5):2..6
    y(1):5
    a(2):1..2
    z(1):6
Result of layout:
    0 -> {b(5):2..6}
    1 -> {a(2):1..2, x(1):4, y(1):5, z(1):6}
Visual presentation:
      bbbbb
     aa xyz

Event collection:
    x(1):1
    b(3):2..4
    a(2):1..2
    c(2):4..5
    y(1):5
Result of layout:
    0 -> {b(3):2..4, x(1):1, y(1):5}
    1 -> {a(2):1..2, c(2):4..5}
Visual presentation:
     xbbby 
     aa cc 

Event collection:
    f(2):1..2
    h(2):1..2
    d(4):1..4
    e(4):2..5
    c(1):6
    a(2):5..6
    g(4):2..5
    b(2):0..1
Result of layout:
    0 -> {d(4):1..4, a(2):5..6}
    1 -> {e(4):2..5, b(2):0..1, c(1):6}
    2 -> {g(4):2..5}
    3 -> {f(2):1..2}
    4 -> {h(2):1..2}
Visual presentation:
     ddddaa
    bbeeeec
      gggg 
     ff    
     hh    

Answer 2

أعتقد أنه في مثل هذا الموقف، من الأفضل التأكد من تنظيم بياناتك بشكل صحيح أولاً ثم عرضها.أعلم أنك تريد تمريرة واحدة، ولكن أعتقد أن النتائج ستكون أفضل بكثير.

على سبيل المثال، قم بتنظيم البيانات في السطور التي ستحتاج إليها ليوم معين وقم بتنظيم الأحداث بأفضل طريقة ممكنة، بدءًا من الأحداث الأطول (لا يلزم عرضها أولاً، ولكنها تحتاج إلى التنظيم أولا) والانتقال إلى أقصر الأحداث.سيسمح لك هذا بعرض مخرجاتك وفقًا لذلك دون إضاعة أي مساحة، وتجنب أيام الأحداث "e".بالإضافة إلى ذلك، ثم:

 bbb
aa cc

أو

aa cc
 bbb

لن يهم لأن x و y يمكن أن تذهب دائما على جانبي bbb أو حتى بين aa و cc

أتمنى أن تجد هذا مفيدا.