Search code examples
c#rangeline-numbers

A C# Implementation of Number Line

NumberLine line = new NumberLine();
line.AddRange(1, 5);
line.AddRange(20, 30);

line.CheckRange(10, 25);

NumberLine is a class which represents a number line. I want to mark on it different ranges of numbers. The CheckRange method should return which parts from 10-25 I marked and which I did not. In this case it should return that 10-20 is not marked, and that 20-25 is marked.

How can I implement an effective implementation of this, which wouldn't do o(n)?

Thank you.

NOTE: This is NOT homework. I need this for my custom database implementation transactions. I'm learning programming alone.

Solution

  • The solution is simple: Add all highlighted values to an AVL or Red-black tree. I mean when you do AddRange(1,3), insert the integer values 1,2 and 3 in the tree.

    When checking ranges, simply lookup the endpoint values. That takes O(log n) which is considerably faster than O(n).

    Note: Insertion and delete all take O(log n).