CODEWITHSUNDEEP
iphoneioscocoa-touchcocoalogic
Anton Unt
Anton Unt

Reputation: 1875

Logic - Need to find overlapping ranges of numbers

Say I have an array of "numbers" object with a "startNo" integer and "endNo" integer.

There can be multiple "numbers" in the array and I want to get a new array with modified objects which will only have the ranges with no overlap.

For eg: if the array has:

number
( startNo:1 endNo:3)
( startNo:1 endNo:7)
( startNo:2 endNo:9)
( startNo:15 endNo:18)
( startNo:50 endNo:60)
( startNo:55 endNo:65)

I want to get an array like this:

number
( startNo:1 endNo:9)
( startNo:15 endNo:18)
( startNo:50 endNo:65)

I have been trying hands on different approaches with structs, fors and everything but all I get is multi-level-confusion.

I am working on objective-C platform if that helps

To add: The startPage can be a big number and endPage can be a small number.

Upvotes: 1

Views: 727

Answers (5)

Vijay
Vijay

Reputation: 247

//It's written in C# language. But concept can be implemented in any programming language.

public class Range
{
    public int startNo { get; set; }
    public int stopNo { get; set; }

    public Range(int start, int stop)
    {
        startNo = start;
        stopNo = stop;
    }
}

        public void GetUniqueRanges()
    {
        var rangeList = new List<Range>();
        rangeList.Add(new Range(7,4));
        rangeList.Add(new Range(3, 15));
        rangeList.Add(new Range(54, 35));
        rangeList.Add(new Range(45, 60));
        rangeList.Add(new Range(60,75));
        rangeList.Add(new Range(76,100));
        rangeList.Add(new Range(6,10));
        rangeList.Add(new Range(16,24));
        rangeList.Add(new Range(19,34));

        var sorted = new List<Range>();
        foreach (var range in rangeList)
        {
            var item = new Range(Math.Min(range.startNo, range.stopNo), Math.Max(range.startNo, range.stopNo));
            sorted.Add(item);
        }
        var result = new List<Range>();
        sorted = sorted.OrderBy(x => x.startNo).ToList();
        var counter = sorted.Count;
        for (var i = 0; i < counter; )
        {
            var item = new Range (sorted[i].startNo, sorted[i].stopNo );
            var j = i + 1;
            for (; j < counter; j++)
            {
                if (sorted[j].startNo <= item.stopNo)
                {
                    item.stopNo =Math.Max(item.stopNo, sorted[j].stopNo);
                }
                else
                {

                    break;
                }
            }
            i = j;
            result.Add(item);
        }
    }

Upvotes: 0

Anoop Vaidya
Anoop Vaidya

Reputation: 46543

Assuming your class is MyNumbers and is like this :

@interface MyNumbers : NSObject
@property NSInteger startNumber;
@property NSInteger endNumber;

- (id)initWithStartNumber:(NSInteger)start withEnd:(NSInteger)end;

@end

And the way to merge:

- (void)yourMethod{

    MyNumbers *obj1=[[MyNumbers alloc]initWithStartNumber:1 withEnd:3];
    MyNumbers *obj2=[[MyNumbers alloc]initWithStartNumber:1 withEnd:7];
    MyNumbers *obj3=[[MyNumbers alloc]initWithStartNumber:2 withEnd:9];
    MyNumbers *obj4=[[MyNumbers alloc]initWithStartNumber:15 withEnd:18];
    MyNumbers *obj5=[[MyNumbers alloc]initWithStartNumber:50 withEnd:60];
    MyNumbers *obj6=[[MyNumbers alloc]initWithStartNumber:55 withEnd:65];

    NSArray *array=@[obj1,obj2,obj3,obj4,obj5,obj6];
    NSMutableArray *mergedArray=[NSMutableArray arrayWithObject:array[0]];

    for (NSInteger index=1; index<array.count; index++) {
        MyNumbers *currentNumber=array[index];
        MyNumbers *previousNumber=array[index-1];

        if (currentNumber.startNumber<=previousNumber.endNumber) {
            previousNumber.endNumber=currentNumber.endNumber;
            [mergedArray replaceObjectAtIndex:mergedArray.count-1 withObject:previousNumber];
        }
        else{
            [mergedArray addObject:currentNumber];
        }
    }

    for(MyNumbers *element in mergedArray){
        NSLog(@"startNo:%d endNo:%d",element.startNumber, element.endNumber);
    } 
}

Output:

2013-03-14 17:14:05.040 Inheritance[34234:303] startNo:1 endNo:9
2013-03-14 17:14:05.041 Inheritance[34234:303] startNo:15 endNo:18
2013-03-14 17:14:05.041 Inheritance[34234:303] startNo:50 endNo:65

Upvotes: 2

Thanakron Tandavas
Thanakron Tandavas

Reputation: 5683

A simple approach to solve this:

  1. Create a new empty array (let's name it: tmp).
  2. Put first array's startNo and endNo to tmp.
  3. Take second array's startNo and endNo. Then, decide whether they overlap with the ones in tmp or not. (If they don't overlap, insert both of them at the end of tmp.)
  4. Repeat the steps for every arrays.
  5. tmp will now hold the all ranges with no overlap.

Upvotes: 1

V-Xtreme
V-Xtreme

Reputation: 7333

Just quick idea not tested :

1.Get the smallest start number say sn and corresponding end no say en.

2.Go on checking next objects if start no is less than sn then ignore the start no . And if end number is greater than en then store new end number to your en .

3.This will gives you your object .

4.If the start number is greater than en then create a new object to add into the array .

this should work .tell me if you have further problems

Upvotes: 1

drtf
drtf

Reputation: 1976

It's a classical algorithms course question..

Sort the arrays by descending order of the first (smallest) value. keep track of two variables: start segment,end segment.

Every turn pick an array and check for start and end numbers and figure out if its in the segment or not.

This way it is possible to find the overlaps

Good Luck

Upvotes: 2

Related Questions