java - 如何找到可以执行的最大参与者人数？

Question

我正在尝试解决具有以下描述的问题:

同一时间只能有一个人上台表演，每个参与者的到达时间和持续时间以数组的形式给出。找出可以执行的参与者的最大数量。

例子:

arrival time: [1,3,3,5,7]

duration: [2,2,1,2,1]

answer would be 4, as 1-3; 3-5 or 3-4; 5-7; 7-8

所以从这里，我可以找到每个参与者的退出时间。当时间重叠时，如何找到可能的最大事件数。

我试过的代码是:

int count = 1;
        
for(int i=0;i<entry.size()-1;i++) {
    if(entry.get(i) < exit.get(i+1)) {
        count++;
    }
}
        
return count;

我使用 arrival + duration 找到了退出列表，但是很多测试都失败了。上面的例子通过了，但可能会有重叠时间可能有更多参与者的情况。

我不知道如何继续。

Answer 1

更新了答案，因为添加了一个新的测试用例，明确表示如果表演者的到达时间相同，则可以重新排序。第二次更新:对每个表演者的结束时间(到达+持续时间)的输入进行排序。保留当前表演者的结束时间。只有在当前表演者结束后到达的表演者才能表演。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class LifeGig {

    public static class Performer {
        int arrival, duration;

        Performer(int arrival, int duration) {
            this.arrival = arrival;
            this.duration = duration;
        }

        @Override
        public String toString() {
            return "Performer [arrival=" + arrival + ", duration=" + duration + "]";
        }
    }

    public List<Performer> program(int[] entry,int[] duration)
    {
        List<Performer> performers=new ArrayList<>();
        for(int i=0;i<entry.length;i++)
        {
            performers.add(new Performer(entry[i],duration[i]));
        }
        Collections.sort(performers, new Comparator<Performer>() {
            @Override
            public int compare(Performer p1, Performer p2) {
                return Integer.compare(p1.arrival+p1.duration, p2.arrival+p2.duration);
            }
        });
        List<Performer> festival=new ArrayList<>();
        System.out.println(performers);
        int currentTime = 1;
        for (Performer p:performers) {
            if (p.arrival >= currentTime) {
                currentTime = p.arrival+p.duration;
                festival.add(p);
            }
        }
        return festival;
    }
    public static void test1()
    {
        int[] entry = new int[] {1,3,3,5,7};
        int[] duration = new int[] {2,2,1,2,1};
        List<Performer> festival=new LifeGig().program(entry,duration);
        System.out.println("Count (Expected=4): " + festival.size());
        System.out.println("lineup:"+festival);
    }

    public static void test2()
    {
        int[] entry = new int[] {1, 1, 1, 1, 4};
        int[] duration = new int[] {10, 3, 6, 4, 2};
        List<Performer> festival=new LifeGig().program(entry,duration);
        System.out.println("Count (Expected=2): " + festival.size());
        System.out.println("lineup:"+festival);
    }
    public static void test3()
    {
        int[] entry = new int[] {1,2,3,4};
        int[] duration = new int[] {10, 1,1,1,};
        List<Performer> festival=new LifeGig().program(entry,duration);
        System.out.println("Count (Expected=3): " + festival.size());
        System.out.println("lineup:"+festival);

    }

    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

}