CODEWITHSUNDEEP
c#
LeeroyJenkins313
LeeroyJenkins313

Reputation: 1

Find the least amount of intervals which cover highest range

I would like to ask for a hint how to approach in solving this task:

I have intervals ordered by min. value eg: ([1,5],[2,9],[6,7],[8,16],[11,15], [18,20]). I should pick minimal amount of intervals, which cover the largest range.

So I should store these: ([1,5],[2,9],[8,16],[18,20]). Interval [6,7] is not stored, because it is covered by interval [2,9]. Interval [11,15] is not stored, because it is covered by [8,16].

How should I approach in solving this? Thank you:)

Upvotes: 0

Views: 127

Answers (3)

fubo
fubo

Reputation: 45947

Linq approach

int[][] input = new[] { new[] { 1, 5 }, new[] { 2, 9 }, new[] { 6, 7 }, new[] { 8, 16 }, new[] { 11, 15 }, new[] { 18, 20 } };
int[][] result = input.Where((i1, x1) => !input.Where((i2, x2) => x1 != x2 && i2[0] <= i1[0] && i2[1] >= i1[1]).Any()).ToArray();

https://dotnetfiddle.net/x1xosT

Update: Thanks to @yuriy-faktorovich I've a added a <= and >= comparison instead < and >. Also removed the comparison with itselve.

Upvotes: 1

Yuriy Faktorovich
Yuriy Faktorovich

Reputation: 68687

I believe there could be local maximums, so I wrote the recursive function to look at different options

static List<(int lower,int higher)> Minimize(List<(int lower, int higher)> list, int i = 0)
{
    //past last item
    if (i >= list.Count) return list;
    
    if (( i > 0 && list[i - 1].higher >= list[i].higher) || 
        (i + 1 < list.Count && list[i + 1].lower == list[i].lower) ||
        (i > 0 && i + 1 < list.Count && list[i + 1].lower - list[i - 1].higher <= 1))
    {
        var newList = list.ToList();
        newList.RemoveAt(i);
        var minimizedNewList = Minimize(newList);
        var minimizedCurrentList = Minimize(list, i + 1);
        return minimizedNewList.Count < minimizedCurrentList.Count ? minimizedNewList : minimizedCurrentList;
    }
    else return Minimize(list, i + 1);
}

You can test with the following

var testData = new[] {(1, 5), (2, 9), (6,7), (8, 16), (11, 15), (18, 20)};

var result  = Minimize(testData.ToList());

foreach (var valueTuple in result)
{
    WriteLine(valueTuple);
}

WriteLine("----------------------------");

testData = new[] { (1, 5), (5, 6), (6, 7) };

result = Minimize(testData.ToList());

foreach (var valueTuple in result)
{
    WriteLine(valueTuple);
}

WriteLine("----------------------------");

testData = new[] { (1, 10), (5, 6) };

result = Minimize(testData.ToList());

foreach (var valueTuple in result)
{
    WriteLine(valueTuple);
}

WriteLine("----------------------------");

testData = new[] { (1, 10), (1, 20) };

result = Minimize(testData.ToList());

foreach (var valueTuple in result)
{
    WriteLine(valueTuple);
}

Here's a fiddle https://dotnetfiddle.net/EC5BrW

Upvotes: 0

Arkrez
Arkrez

Reputation: 1

It looks like all you need to do is keep track of the current highest range and only store numbers that are higher.

So the first highest number would be 5 so you store it, then add 9 and make it the highest number, then you reach 7 which is less than 9, so it's not stored, then you add 16 and make it the highest, 15 is less than 16, so skip it, and then finally add 20.

idk what language you're using, but the code would look something like.

foreach(var item in dataset)
{
    if(item[1] > highest)
    {
        savedItems.Add(item);
        highest = item[1];
    }

}

Upvotes: 0

Related Questions