Trick to randomly generate disjoint ranges
source link: https://codeforces.com/blog/entry/111328
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Trick to randomly generate disjoint ranges
Recently, I was solving a problem that involved disjoint ranges. And while stress testing my solution I found a simple trick to fairly and efficiently generate such ranges.
Let us first examine a set of disjoint ranges: [{2,3}, {6, 7}, {4, 5}]. If we list their endpoints in order, we get a sequence of integers, where adjacent integers are paired together to form a range: [2,3, 4,5, 6,7]
It follows from this observation that you can generate N disjoint ranges by first generating unique integers (duplicates will affect the disjoint condition), and then "matching" adjacent integers together.
Here is some Python code:
As an additional advantage, the output is sorted.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK