Finding as many pairs as possible
algorithm, graph, java
Solution
No need to create graph here, this problem can be solved well on intervals structure. Sort people by ascending order of their leaving time(ending point of interval). Then iterate over them in that sorted order: if current person is not intersecting with anyone, then he should be removed. If he is intersecting with more than one person, take as a pair one of them who has earliest leaving time. During iteration you should compare each person only with next ones.
Proving this approach is not so difficult, so I hope you can prove it yourself. Regarding running time, simple solution will be O(N^2), however I think that it can be reduced to O(N * logN). Anyway, O(N^2) will fit in 10 seconds on a normal PC.
Problem
I'm trying to solve a problem but unfortunately my solution is not really the best for this task. Task: At a party there are N guests ( 0 < N < 30000 ). All guests tell when they get to the party and when they leave (for example [10;12]). The task is to take photos of as many people as possible at the party. On a photo there can only be 2 people (a pair) and each person can only be on exactly one photo. Of course, a photo can only be taken when the two persons are at the party at the same time. This is the case when their attendance intervals overlap. My idea: I wrote a program which from the intervals creates a graph of connections. From the graph I search for the person who has the least number of connections. From the connected persons I also select the person who has the least connections. Then these two are chosen as a pair on a photo. Both are removed from the graph. The algorithm runs until no connections are left. This approach works however there is a 10 secs limit for the program to calculate. With 1000 entries it runs in 2 secs, but even with 4000 it takes a lot of time. Furthermore, when I tried it with 25000 data, the program stops with an out of memory error, so I cannot even store the connections properly. I think a new approach is needed here, but I couldn't find an other way to make this work. Can anyone help me to figure out the proper algorithm for this task? Thank you very much! Sample Data: ``` 10 1 100 2 92 3 83 4 74 5 65 6 55 7 44 8 33 9 22 10 11 ``` The first line is the number of guests the further data is the intervals of people at the party.