The weekly challenge 298 - Task 2: Right Interval

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-298/#TASK2
 3 #
 4 # Task 2: Right Interval
 5 # ======================
 6 #
 7 # You are given an array of @intervals, where $intervals[i] = [starti, endi]
 8 # and each starti is unique.
 9 #
10 # The right interval for an interval i is an interval j such that startj >=
11 # endi and startj is minimized. Please note that i may equal j.
12 #
13 # Write a script to return an array of right interval indices for each interval
14 # i. If no right interval exists for interval i, then put -1 at index i.
15 #
16 ## Example 1
17 ##
18 ## Input: @intervals = ([3,4], [2,3], [1,2])
19 ## Output: (-1, 0, 1)
20 ##
21 ## There is no right interval for [3,4].
22 ## The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start
23 ## that is >= end1 = 3.
24 ## The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start
25 ## that is >= end2 = 2.
26 #
27 ## Example 2
28 ##
29 ## Input: @intervals = ([1,4], [2,3], [3,4])
30 ## Output: (-1, 2, -1)
31 ##
32 ## There is no right interval for [1,4] and [3,4].
33 ## The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start
34 ## that is >= end1 = 3.
35 #
36 ## Example 3
37 ##
38 ## Input: @intervals = ([1,2])
39 ## Output: (-1)
40 ##
41 ## There is only one interval in the collection, so it outputs -1.
42 #
43 ## Example 4
44 ##
45 ## Input: @intervals = ([1,4], [2, 2], [3, 4])
46 ## Output: (-1, 1, -1)
47 #
48 ############################################################
49 ##
50 ## discussion
51 ##
52 ############################################################
53 #
54 # For each interval in the list, we check all the intervals in
55 # the list whether it has a new minimum start that is >= the end
56 # of the first interval. At the end, return the index of that
57 # minimum if it exists, otherwise -1.
58 
59 use strict;
60 use warnings;
61 
62 right_interval([3,4], [2,3], [1,2]);
63 right_interval([1,4], [2,3], [3,4]);
64 right_interval([1,2]);
65 right_interval([1,4], [2, 2], [3, 4]);
66 
67 sub right_interval {
68    my @intervals = @_;
69    print "Input: (";
70    foreach my $interval (@intervals) {
71       print "[" . join(", ", @$interval) . "],";
72    }
73    print ")\n";
74    my @result = ();
75    foreach my $i (0..$#intervals) {
76       my $min = undef;
77       my $index = -1;
78       foreach my $j (0..$#intervals) {
79          if($intervals[$j]->[0] >= $intervals[$i]->[1]) {
80             if(defined($min)) {
81                if($min >  $intervals[$j]->[0]) {
82                   $min = $intervals[$j]->[0];
83                   $index = $j;
84                }
85             } else {
86                $min = $intervals[$j]->[0];
87                $index = $j;
88             }
89          }
90       }
91       push @result, $index;
92    }
93    print "Output: (" . join(", ", @result) . ")\n";
94 }