Task — Conflict intervals

You are given a list of intervals. Write a script to find out if the current interval conflicts with any of the previous intervals.

Examples

Example 1:
Input: @Intervals = [ (1,4), (3,5), (6,8), (12, 13), (3,20) ]
Output: [ (3,5), (3,20) ]
    - The 1st interval (1,4) do not have any previous 
	intervals to compare with, so skip it.
    - The 2nd interval (3,5) does conflict with previous 
	interval (1,4).
    - The 3rd interval (6,8) do not conflicts with any of
	the previous intervals (1,4) and (3,5), so skip it.
    - The 4th interval (12,13) again do not conflicts with
	any of the previous intervals (1,4), (3,5) and (6,8), so skip it.
    - The 5th interval (3,20) conflicts with the first
	interval (1,4).

Example 2:
Input: @Intervals = [ (3,4), (5,7), (6,9), (10, 12), (13,15) ]
Output: [ (6,9) ]
    - The 1st interval (3,4) do not have any previous
	intervals to compare with, so skip it.
    - The 2nd interval (5,7) do not conflicts with the
	previous interval (3,4), so skip it.
    - The 3rd interval (6,9) does conflict with one of the
	previous intervals (5,7).
    - The 4th interval (10,12) do not conflicts with any
	of the previous intervals (3,4), (5,7) and (6,9), so
	skip it.
    - The 5th interval (13,15) do not conflicts with any
	of the previous intervals (3,4), (5,7), (6,9) and 
	(10,12), so skip it.

Analysis

I did not submit a solution at the time, but have written this later

There are 6 possible combinations of 2 ranges:

     |xxxxx|
xxxx |     |
  xxx|x    | 
    x|xxxxx|x
     | xxx |
     |   xx|xxx
     |     | xxxx

If you consider the red range, the blue range doesn't conflict with it if:

• The blue range ends before the red range starts, or
• The blue range starts after the red range ends.

And that is just what my solution does, checking each possible pair of intervals.

The last six examples I have shown correspond to the six cases in the diagram above.

Try it 

Try running the script with any input:

Your @Intervals =

example: (1, 5), (6, 10), (5, 6)

⤡

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2021-08-23
use utf8;     # Week 127 - task 2 - Conflict intervals
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

conflict_intervals((1,4), (3,5), (6,8), (12, 13), (3,20));
conflict_intervals((3,4), (5,7), (6,9), (10, 12), (13,15));

conflict_intervals((1, 3), (4, 6));
conflict_intervals((1, 4), (4, 6));
conflict_intervals((1, 7), (4, 6));
conflict_intervals((5, 5), (4, 6));
conflict_intervals((5, 8), (4, 6));
conflict_intervals((7, 8), (4, 6));

sub conflict_intervals {
    
    my (@bounds, $j, $k, $input, $output, $pair);
    
    # initialise
    @bounds = @_;
    $input = $output = '';

    # loop over ranges
    for ($j = 0; $j < @bounds; $j += 2) {
        $pair = qq[($bounds[$j], $bounds[$j + 1])]; 
        $input .= qq[$pair, ];
        
        # loop over all ranges before this one
        next if $j == 0;
        for ($k = 0; $k < $j; $k += 2) {
            
            # condition for no conflict (see blog)
            next if $bounds[$k + 1] < $bounds[$j]
                or $bounds[$k] > $bounds[$j + 1];
            $output .= qq[$pair conflicts with ($bounds[$k], $bounds[$k + 1])\n];
        }       
    }
    
    # show results
    $output = 'No conflicts ' unless $output;
    say qq[\nInput:  \@Intervals = \[] . substr($input, 0, -2) . ']';
    say qq[Output: \n] . substr($output, 0, -1);
}

Output

Input:  @Intervals = [(1, 4), (3, 5), (6, 8), (12, 13), 
   (3, 20)]
Output: 
(3, 5) conflicts with (1, 4)
(3, 20) conflicts with (1, 4)
(3, 20) conflicts with (3, 5)
(3, 20) conflicts with (6, 8)
(3, 20) conflicts with (12, 13)

Input:  @Intervals = [(3, 4), (5, 7), (6, 9), (10, 12), 
   (13, 15)]
Output: 
(6, 9) conflicts with (5, 7)

Input:  @Intervals = [(1, 3), (4, 6)]
Output: 
No conflicts

Input:  @Intervals = [(1, 4), (4, 6)]
Output: 
(4, 6) conflicts with (1, 4)

Input:  @Intervals = [(1, 7), (4, 6)]
Output: 
(4, 6) conflicts with (1, 7)

Input:  @Intervals = [(5, 5), (4, 6)]
Output: 
(4, 6) conflicts with (5, 5)

Input:  @Intervals = [(5, 8), (4, 6)]
Output: 
(4, 6) conflicts with (5, 8)

Input:  @Intervals = [(7, 8), (4, 6)]
Output: 
No conflicts