Most Visited Sector in a Circular Track

🏠 ⬅️ ➡️

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The ith round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Example 1:

Input: n = 4, rounds = [1,3,1,2] Output: [1,2] Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows: 1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon) We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.

Example 2:

Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2] Output: [2]

Example 3:

Input: n = 7, rounds = [1,3,5,7] Output: [1,2,3,4,5,6,7]

Constraints:

  • 2 <= n <= 100
  • 1 <= m <= 100
  • rounds.length == m + 1
  • 1 <= rounds[i] <= n
  • rounds[i] != rounds[i + 1] for 0 <= i < m
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 4, m = 4
    integer, dimension(m+1) :: rounds = (/ 1, 3, 1, 2 /)
    integer, dimension(:), allocatable :: visited_sectors
    integer :: i

    allocate(visited_sectors(n))

    call solve(n, rounds, visited_sectors)

    do i = 1, size(visited_sectors)
        write (unit=error_unit, fmt='(I0, 1X)') visited_sectors(i)
    end do

contains

    subroutine solve(n, rounds, visited_sectors)
        implicit none
        integer, value :: n, rounds(m+1)
        integer, intent(out) :: visited_sectors(n)
        integer :: current_sector, next_sector

        current_sector = rounds(1)
        visited_sectors(current_sector) = visited_sectors(current_sector) + 1

        do i = 2, m+1
            next_sector = rounds(i)
            if (next_sector > current_sector) then
                ! circulate the track in ascending order of sector numbers
                ! in the counter-clockwise direction
                visited_sectors(next_sector) = visited_sectors(next_sector) + 1
                current_sector = next_sector
            else
                ! circulate the track in descending order of sector numbers
                ! in the clockwise direction
                visited_sectors(n + 1 - next_sector) = visited_sectors(n + 1 - next_sector) + 1
                current_sector = n + 1 - next_sector
            end if
        end do
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module most_visited_sectors
  implicit none
contains
  subroutine solve(n, rounds, result)
    integer, intent(in) :: n, rounds(n + 1)
    integer, intent(out) :: result(n)

    integer :: i, j, current_sector, next_sector
    integer :: visited_sectors(n)

    ! Initialize the visited sectors array
    do i = 1, n
      visited_sectors(i) = 0
    end do

    ! Start at sector 1
    current_sector = 1

    ! Loop through each round
    do i = 1, n
      ! Find the next sector
      next_sector = rounds(i)

      ! Increment the visited count for the current sector
      visited_sectors(current_sector) = visited_sectors(current_sector) + 1

      ! Update the current sector
      current_sector = next_sector
    end do

    ! Sort the visited sectors array in ascending order
    call sort(visited_sectors)

    ! Copy the sorted visited sectors array to the result array
    do i = 1, n
      result(i) = visited_sectors(i)
    end do
  end subroutine solve

  subroutine sort(array)
    integer, intent(inout) :: array(:)
    integer :: i, j, temp

    do i = 1, size(array) - 1
      do j = i + 1, size(array)
        if (array(i) > array(j)) then
          temp = array(i)
          array(i) = array(j)
          array(j) = temp
        end if
      end do
    end do
  end subroutine sort
end module most_visited_sectors

program test
  use most_visited_sectors
  implicit none

  integer, parameter :: n = 4
  integer, parameter :: rounds(n + 1) = [1, 3, 1, 2]
  integer :: result(n)

  call solve(n, rounds, result)

  write (*, "(A, I0, A)") "The most visited sectors are: ", result, "."
end program test
🌐 Data from online sources 
def busy_student(start_time, end_time, query_time):
    count = 0
    for i in range(len(start_time)):
        if start_time[i] <= query_time <= end_time[i]:
            count += 1
    return count

The algorithm consists of iterating through the startTime and endTime arrays in parallel, by checking if the queryTime lies within the range of startTime[i] and endTime[i]. If it's within the range, increment the count. Finally, return the count as the result. The code is quite similar across the different languages.

🌐 Data from online sources 
int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
    int count = 0;
    for (int i = 0; i < startTime.size(); i++) {
        if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
            count++;
        }
    }
    return count;
}

The algorithm consists of iterating through the startTime and endTime arrays in parallel, by checking if the queryTime lies within the range of startTime[i] and endTime[i]. If it's within the range, increment the count. Finally, return the count as the result. The code is quite similar across the different languages.