|
 |
| Chris Wladyszewski |
This page is dedicated for developers. Please, forgive us but this page is only in English.
You can find here some algorithms. They have nothing to do with David system.
We hope it may be helpful for someone.
You can do with these algorithms anything you want as well as the source codes.
Krzysztof (Chris) Wladyszewski is the author of all algorithms included in this page.
Problem 1
Write a program that takes a list of integer ranges and an additional range
and prints all non-overlapping ranges from the additional range.
For example, given a list or ranges A=[6;9], B=[14;20], C=[21;24], D=[12;22] and a new range X=[7;27],
the program should print [10;11], [25;27].
The graphic explanation of the algorithm is shown below.
1. Get the list of input ranges.
2. Sort the ranges. This order is vital to the algorithm.
It's good idea to keep them sorted during adding them to the list.
3. Merge overlapping ranges. It's easy to see now whay the order of the ranges is so important.
4. Trim the ranges to the size of the main range.
5. Take complement of ranges.
6. Remove original ranges. Final ranges are ready!
Below you can find a sample implementation of the above algorithm.
The program was written in C++: problem1.
|
