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.

This review may cover either or both challenges for this week.

I am sorry that the 'Try it' feature is currently working very slowly or not at all owing to some issue with my web hosting provider.

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);
}

14 lines of code

Output from script

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