Search for as many pairs as possible

Question

I am trying to solve a problem, but unfortunately my solution is not very suitable for this task.

Task:

There are N guests at the party (0 <N <30,000). All guests tell when they get to the party and when they leave (for example, [10; 12]). The challenge is to photograph as many people as possible at the party. There can only be 2 people (couple) in the photo, and each person can only be in one photo. Of course, a photograph can only be taken when both participants are at a party. This is the case when the intervals of their visits overlap.

My idea: I wrote a program that creates a connection schedule from intervals. On the graph, I am looking for the person with the least number of connections. From the connected persons, I also choose the person with the smallest connections. Then these two are selected as a pair in the photo. Both of them are removed from the chart. The algorithm runs until the connections are deleted.

This approach works, but there is a 10 second limit to program calculation. With 1000 records, it works after 2 seconds, but even with 4000 it takes a lot of time. In addition, when I tried it with 25,000 data, the program stops with an out-of-memory error, so I can’t even save the connections correctly.

I think a new approach is needed here, but I could not find another way to do this work.

Can someone help me find the right 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 additional data is the intervals of people on the side.

Answer 1

There is no need to create a graph here, this problem can be solved well on the interval structure. Sort people by increasing their departure time (endpoint of the interval). Then iterate over them in this orderly order: if the current person does not intersect with anyone, he must be removed. If it intersects with more than one person, take as a couple one of them who has the earliest exit time. During the iteration, you should compare each person only with the following.

The proof of this approach is not so complicated, so I hope you can prove it yourself. As for runtime, a simple solution would be O (N ^ 2), but I think it can be reduced to O (N * logN). In any case, O (N ^ 2) will fit in 10 seconds on a regular PC.

Answer 2

Sounds like a classic max match for me.

You build a graph in which people who can be depicted together (their time intervals intersect) are connected to an edge, and then find the maximum match, for example, using Edmond Blossom .

I would not say that it is quite easy to implement. However, you can evaluate this pretty well using the Kuhn algorithm for maximum consistency in two-way graphs. It is really easy to implement, but it won’t give you an exact solution.

Answer 3

I have a very simple idea:

Suppose a party takes Xh, makes X sets for every hour, and adds the right people to them. Of course, people who will be there for more than an hour will be in several sets. Now, if there are two sets “together” with an even number of ppl, you can take n / 2 photos for each set. If there are 2 sets of an odd number of people, you are looking for someone to be on each of these 2 sets, and move it to one of them (so that you have 2 even sets of people who will be in the same party time).

Do not forget to delete all used ppl (consider some class - Man with lists of all his hours).

My idea should probably be expanded to a more advanced moving people algorithm through more than one adjacent set.

Answer 4

I think the following can do:

First, read all the guest data and sort them into an array, leaving time in ascending order. Then take the first element of the array and swipe through the following elements until the very first match is found (the next time for guest recording is less than the time that the guests were kept), if it is found, remove both from the array as a couple and report this elsewhere, if not, remove the guest as he cannot be paired at all. Repeat until the array becomes empty.

In the worst case, it is also N ^ 2, since the side can be like [1,2],[3,4],... , where guests cannot be connected to each other, and the algorithm will look for all 30,000 guests for nothing all the time . Therefore, I do not think that this is an optimal algorithm, but it should give an exact answer.

Answer 5

You say that you already have a view of the graph structure. I assume that your peaks represent the guest and the interval of their stay at the party, and the edges represent the overlap of the corresponding intervals. What you need to solve is a theoretical theorem, the problem of maximum correspondence , which was solved earlier.

However, as stated in my comments above, I think that you can use the properties of the problem, especially transit-like "if A leaves before leaves B and leaves B before C, then A and C will not meet, either" as follows :

Wait until the next guest, not yet taken by the guest, is going to leave, then take a picture of this with someone who will leave next to those present.

Answer 6

You may be able to think about the earliest time when a photograph can be taken: this is the time when the second person comes to the party.

So, as a photographer, we move on to be the first person and wait. Whenever a person comes, take photos with him and all the other people at the party. Since a person appears only once, you will not have duplicates.

When taking a photo (for example, repeating a guest list), delete those guests who actually left the party.