Task — Right interval

You are given an array of @intervals, where $intervals[i] = [$starti, $endi] and each $starti is unique. The right interval for an interval $i is an interval $j such that $startj >= $endi and $startj is minimized. Please note that $i may equal $j.

Write a script to return an array of right interval indices for each interval $i. If no right interval exists for interval $i, then put -1 at index $i.

Examples

Example 1
Input: @intervals = ([3,4], [2,3], [1,2])
Output: (-1, 0, 1)
There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 
   is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 
   is the smallest start that is >= end2 = 2.

Example 2
Input: @intervals = ([1,4], [2,3], [3,4])
Output: (-1, 2, -1)
There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 
   is the smallest start that is >= end1 = 3.

Example 3
Input: @intervals = ([1,2])
Output: (-1)
There is only one interval in the collection, so it 
   outputs -1.

Example 4
Input: @intervals = ([1,4], [2, 2], [3, 4])
Output: (-1, 1, -1)

Analysis

The hardest thing about this challenge was understanding what is required, although the examples help a lot.

The obvious way to do it is to loop $i over @intervals, and for each interval loop again using $j lto find the least $j->[start] which isn't less than $i->[end]. So that's what I did.

Try it 

Try running the script with any input:

Your @intervals =

example: [3,4], [2,3], [1,2]

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-12-02
use utf8;     # Week 298 - task 2 - Right interval
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

right_interval([3, 4], [2, 3], [1, 2]);
right_interval([1, 2]);
right_interval([1, 4], [2, 2], [3, 4]);
right_interval([1, 1], [12, 12], [23, 23], [34, 34]);
right_interval([9, 9], [8, 8], [7, 7], [6, 6]);

sub right_interval {
    
    my (@ints, $i, $j, @right_int, $input, $best, $best_j);
    @ints = @_;
    
    # loop over intervals
    I: for ($i = 0; $i <= $#ints; $i ++) {
        
        # loop over each potential right intervals
        $best = $best_j = 1e6;
        for ($j = 0; $j <= $#ints; $j ++) {
            if ($ints[$j]->[0] >= $ints[$i]->[1]) {
                
                # save the least
                if ($ints[$j]->[0] < $best) {
                    $best = $ints[$j]->[0];
                    $best_j = $j;
                }
            }
        }
        $right_int[$i] = $best_j < 1e6 ? $best_j : -1;
    }

    # report results
    $input .= qq{[$ints[$_]->[0], $ints[$_]->[1]], } for 0 .. $#ints;
    say qq[\nInput:  \@intervals = ] . substr($input, 0, -2);
    say qq[Output: ] . join(', ', @right_int);
}

Output

Input:  @intervals = [3, 4], [2, 3], [1, 2]
Output: -1, 0, 1

Input:  @intervals = [1, 2]
Output: -1

Input:  @intervals = [1, 4], [2, 2], [3, 4]
Output: -1, 1, -1

Input:  @intervals = [1, 1], [12, 12], [23, 23], [34, 34]
Output: 0, 1, 2, 3

Input:  @intervals = [9, 9], [8, 8], [7, 7], [6, 6]
Output: 0, 1, 2, 3