How to generate a sequence of random pairs such that at most k are mutually intersecting? It is very difficult to find such generators online, hence I want to learn how to make a powerful random generator.
If you mean not completely overlapping, just generate a sorted sequence of 2n elements, and swap k adjacent elements with indexes 2i-1 and 2i for some random i, and then pair a with a , a with a and so on.
I mean not overlapping at all, for example (if k = 2):
[1, 2), [2, 3), [3, 4), [1, 4), [4, 7), [7, 8)
However, this is invalid:
[1, 2), [2, 3), [3, 4), [1, 4), [3, 6]
Then create random pairs, and sort all the points alongside whether they are starting or ending, then check whether there is any point at which there are more than k ranges, and remove all such pairs. To count the number of ranges containing the point, traverse the sorted array, and add 1 if there is a range opening, or subtract 1 if there is a range closing.