Task 1: Merge Intervals
Write a script to merge overlapping intervals from a given list.
Example Output
Input: [2, 7], [3, 9], [10, 12], [15, 19], [18, 22]
Output: [2, 9] [10, 12] [15, 22]
Logic
Sort intervals by their starting values. Iterate through, checking if the current interval overlaps with the next. If it does, update the current interval's upper bound; otherwise, push it to the output and start a new current interval.
Perl Solution
ch-1.pl
sub merge_intervals {
my @intervals = @_;
@intervals = sort { $a->[0] <=> $b->[0] } @intervals;
my @merged_intervals;
my $current_interval = $intervals[0];
for (my $i = 1; $i < scalar @intervals; $i++) {
if ($current_interval->[1] >= $intervals[$i]->[0]) {
$current_interval->[1] = $intervals[$i]->[1] if $current_interval->[1] < $intervals[$i]->[1];
} else {
push @merged_intervals, $current_interval;
$current_interval = $intervals[$i];
}
}
push @merged_intervals, $current_interval;
return \@merged_intervals;
}
Python Solution
ch-1.py
def merge_intervals(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
intervals.sort(key=lambda x: x[0])
merged_intervals = []
current_interval = intervals[0]
for interval in intervals[1:]:
if current_interval[1] >= interval[0]:
current_interval = (current_interval[0],
max(current_interval[1], interval[1]))
else:
merged_intervals.append(current_interval)
current_interval = interval
merged_intervals.append(current_interval)
return merged_intervals
Task 2: Noble Integer
Find if there exists an integer x in a list such that the number of integers greater than x in the list is equal to x.
Example Output
List: [2, 6, 1, 3]
Noble Integer: 2 (since 3 and 6 are greater than 2, count is 2)
Logic
Sort the list. Iterate through the elements. For each index i, the number of elements greater than lst[i] (assuming distinct values or bypassing duplicates) is len(lst) - i - 1. Check if this equals lst[i].
Perl Solution
ch-2.pl
sub find_noble_integer {
my @list = @_;
@list = sort { $a <=> $b } @list;
for (my $i = 0; $i < scalar @list - 1; $i++) {
next if $list[$i] == $list[$i + 1];
if ($list[$i] == scalar(@list) - $i - 1) {
return $list[$i];
}
}
return;
}
Python Solution
ch-2.py
def find_noble_integer(lst: List[int]) -> Union[int, None]:
lst.sort()
for i in range(len(lst) - 1):
if lst[i] == lst[i + 1]:
continue
if lst[i] == len(lst) - i - 1:
return lst[i]
return None