1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
#!/usr/bin/env perl
use strict;
use warnings;
=head1 NAME
PWC 092 Challenge 2
=head1 SYNOPSIS
$ ch-2.pl (1,9),(13,19),(25,26) (8,14)
(1,19),(25,26)
=head1 DESCRIPTION
Given a set of sorted non-overlapping intervals and a new interval, this script
will merge the new interval into the given set of intervals.
=head1 SOLUTION
This script takes in two inputs, the first is a list of intervals and the second
is a new interval that should be added. This script does not currently work
with negative numbers, nor does it do any sanity checking that the input is
sorted and non-overlapping (I didn't get around to checking that.)
This script works by first parsing the existing intervals data into an array of
arrays, with each array holding two values that denote the start and end of the
interval.
It then goes though to determine where to insert the new interval. It checks:
1. Does the new interval just go to the beginning of the set.
2. Does the new interval just go to the end of the set.
3. Does the new interval span all other intervals, so it just becomes the new
interval.
4. The new interval needs to go into the existing set, so starts looping
through existing intervals:
a. Checks if the new interval lands in between the current and the next
interval.
b. Checks if the start of the new interval is before the existing interval, if
so, then set the current interval start to the new interval start.
c. Checks if the end of the new interval is after the existing interval, if so,
then set the end of the current interval to the new interval end.
d. If the new interval connects two intervals, then set the correct beginning
and end, then delete the second interval from the current set.
=head1 AUTHORS
Joel Crosswhite E<lt>joel.crosswhite@ix.netcom.comE<gt>
=cut
my $intervals = $ARGV[0];
my $new_interval = $ARGV[1];
if ((!defined($intervals) || $intervals !~ m/^(\(\d+\,\d+\),)*\(\d+\,\d+\)$/)
|| (!defined($new_interval) || $new_interval !~ m/^\((\d+)\,(\d+)\)$/)) {
print "Usage: ch-2.pl (#,#),(#,#),..(#,#) (#,#)\n";
exit 1;
}
# fetched from input validation regex
my $new_interval_start = $1;
my $new_interval_end = $2;
my @intervals_ds;
extract_intervals($intervals, \@intervals_ds);
# if new interval is before all others....
if ($new_interval_end < $intervals_ds[0][0]) {
splice(@intervals_ds, 0, 0, [$new_interval_start, $new_interval_end]);
# if new inteval is after all others....
} elsif ($new_interval_start > $intervals_ds[-1][1]) {
splice(@intervals_ds, scalar(@intervals_ds), 0,
[$new_interval_start, $new_interval_end]);
# if new interval spans all intervals....
} elsif ($new_interval_start < $intervals_ds[0][0]
&& $new_interval_end > $intervals_ds[-1][1]) {
@intervals_ds = [$new_interval_start, $new_interval_end];
} else {
# go through all existing intervals to see where new one should land
for (my $i = 0; $i < scalar(@intervals_ds) - 1; $i++) {
# new interval falls in between existing intervals
if ($new_interval_start > $intervals_ds[$i][1]
&& $new_interval_end < $intervals_ds[$i + 1][0]) {
splice(@intervals_ds, $i + 1, 0,
[$new_interval_start, $new_interval_end]);
last;
}
# new interval will extend existing interval forward
if ($new_interval_start < $intervals_ds[$i][0]
&& $new_interval_end > $intervals_ds[$i][0]) {
$intervals_ds[$i][0] = $new_interval_start;
}
# new interval will extend existing interval further back
if ($new_interval_end > $intervals_ds[$i][1]
&& $new_interval_end < $intervals_ds[$i + 1][0]) {
$intervals_ds[$i][1] = $new_interval_end;
}
# new interval 'connects' two intervals, requiring the removal of one
if ($new_interval_start < $intervals_ds[$i][1]
&& $new_interval_end > $intervals_ds[$i + 1][0]) {
$intervals_ds[$i][1] = $intervals_ds[$i + 1][1];
splice(@intervals_ds, $i + 1, 1);
}
}
}
print_intervals(\@intervals_ds);
exit 0;
sub extract_intervals {
my ($input, $intervals) = @_;
my $pair_idx = 0;
foreach my $character (split(/[\)\,\(]/, $input)) {
next if $character eq ''; # just skip blank strings that can come in
if ($pair_idx++ % 2 == 0) {
push(@{$intervals}, [$character]);
} else {
push(@{$intervals->[-1]}, $character);
}
}
}
sub print_intervals {
my ($intervals) = @_;
my $output = '';
foreach my $interval (@{$intervals}) {
$output .= sprintf('(%d,%d),', $interval->[0], $interval->[1]);
}
chop($output);
print $output . "\n";
}
|
