The Weekly Challenge 050

Merge Intervals and Noble Integer

Solutions on GitHub

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